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 条
  • [11] Linear Clique-Width for Hereditary Classes of Cographs
    Brignall, Robert
    Korpelainen, Nicholas
    Vatter, Vincent
    JOURNAL OF GRAPH THEORY, 2017, 84 (04) : 501 - 511
  • [12] Comparing Linear Width Parameters for Directed Graphs
    Gurski, Frank
    Rehs, Carolin
    THEORY OF COMPUTING SYSTEMS, 2019, 63 (06) : 1358 - 1387
  • [13] Graphs of linear clique-width at most 3
    Heggernes, Pinar
    Meister, Daniel
    Papadopoulos, Charis
    THEORETICAL COMPUTER SCIENCE, 2011, 412 (39) : 5466 - 5486
  • [14] Obstructions for linear rank-width at most 1
    Adler, Isolde
    Farley, Arthur M.
    Proskurowski, Andrzej
    DISCRETE APPLIED MATHEMATICS, 2014, 168 : 3 - 13
  • [15] Characterising the linear clique-width of a class of graphs by forbidden induced subgraphs
    Heggernes, Pinar
    Meister, Daniel
    Papadopoulos, Charis
    DISCRETE APPLIED MATHEMATICS, 2012, 160 (06) : 888 - 901
  • [16] A Complete Characterisation of the Linear Clique-Width of Path Powers
    Heguernes, Pinar
    Meister, Daniel
    Papadopoulos, Charis
    THEORY AND APPLICATIONS OF MODELS OF COMPUTATION, 2009, 5532 : 241 - +
  • [17] Linear Rank-Width of Distance-Hereditary Graphs
    Adler, Isolde
    Kante, Mamadou Moustapha
    Kwon, O-joung
    GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE, 2014, 8747 : 42 - 55
  • [18] On the linear structure and clique-width of bipartite permutation graphs
    Brandstädt, A
    Lozin, VV
    ARS COMBINATORIA, 2003, 67 : 273 - 281
  • [19] TREE PIVOT-MINORS AND LINEAR RANK-WIDTH
    Dabrowski, K. K.
    Dross, F.
    Jeong, J.
    Kante, M. M.
    Kwon, O-J.
    Oum, S-I.
    Paulusma, D.
    ACTA MATHEMATICA UNIVERSITATIS COMENIANAE, 2019, 88 (03): : 577 - 583
  • [20] TREE PIVOT-MINORS AND LINEAR RANK-WIDTH
    Dabrowski, Konrad K.
    Dross, Francois
    Jeong, Jisu
    Kante, Mamadou M.
    Kwon, O-joung
    Oum, Sang-il
    Paulusma, Daniel
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2021, 35 (04) : 2922 - 2945
123