On the relationship between NLC-width and linear NLC-width

被引：35
|
作者：
Gurski, F [1 ]
Wanke, E [1 ]
机构：
[1] Univ Dusseldorf, Inst Comp Sci, D-40225 Dusseldorf, Germany
来源：
THEORETICAL COMPUTER SCIENCE | 2005年 / 347卷 / 1-2期
关键词：
NLC-width; NLCT-width; linear NLC-width; clique-width; linear clique-width;
D O I：
10.1016/j.tcs.2005.05.018
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
In this paper, we consider NLC-width, NLCT-width, and linear NLC-width bounded graphs. We show that the set of all complete binary trees has unbounded linear NLC-width and that the set of all co-graphs has unbounded NLCT-width. Since trees have NLCT-width 3 and co-graphs have NLC-width 1, it follows that the family of linear NLC-width bounded graph classes is a proper subfamily of the family of NLCT-width bounded graph classes and that the family of NLCT-width bounded graph classes is a proper subfamily of the family of NLC-width bounded graph classes. (c) 2005 Elsevier B.V. All rights reserved.
引用
收藏
页码：76 / 89
页数：14
相关论文
共 22 条
  • [1] Directed NLC-width
    Gurski, Frank
    Wanke, Egon
    Yilmaz, Eda
    THEORETICAL COMPUTER SCIENCE, 2016, 616 : 1 - 17
  • [2] On a disparity between relative cliquewidth and relative NLC-width
    Mueller, Haiku
    Urner, Ruth
    DISCRETE APPLIED MATHEMATICS, 2010, 158 (07) : 828 - 840
  • [3] Characterizations for restricted graphs of NLC-width 2
    Gurski, Frank
    THEORETICAL COMPUTER SCIENCE, 2007, 372 (01) : 108 - 114
  • [4] On powers of graphs of bounded NLC-width (clique-width)
    Suchana, Karol
    Todinca, Ioan
    DISCRETE APPLIED MATHEMATICS, 2007, 155 (14) : 1885 - 1893
  • [5] The NLC-width and clique-width for powers of graphs of bounded tree-width
    Gurski, Frank
    Wanke, Egon
    DISCRETE APPLIED MATHEMATICS, 2009, 157 (04) : 583 - 595
  • [6] Characterizations for co-graphs defined by restricted NLC-width or clique-width operations
    Gurski, F
    DISCRETE MATHEMATICS, 2006, 306 (02) : 271 - 277
  • [7] Linear rank-width and linear clique-width of trees
    Adler, Isolde
    Kante, Mamadou Moustapha
    THEORETICAL COMPUTER SCIENCE, 2015, 589 : 87 - 98
  • [8] Between clique-width and linear clique-width of bipartite graphs
    Alecu, Bogdan
    Kante, Mamadou Moustapha
    Lozin, Vadim
    Zamaraev, Viktor
    DISCRETE MATHEMATICS, 2020, 343 (08)
  • [9] On the relationship between clique-width and treewidth
    Corneil, DG
    Rotics, U
    SIAM JOURNAL ON COMPUTING, 2005, 34 (04) : 825 - 847
  • [10] Linear Rank-Width and Linear Clique-Width of Trees
    Adler, Isolde
    Kante, Mamadou Moustapha
    GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE, WG 2013, 2013, 8165 : 12 - 25
123