Well-quasi-ordering Does Not Imply Bounded Clique-width

被引：5
|
作者：
Lozin, Vadim V. [1 ]
Razgon, Igor [2 ]
Zamaraev, Viktor [3 ]
机构：
[1] Univ Warwick, Math Inst, Coventry CV4 7AL, W Midlands, England
[2] Univ London, Dept Comp Sci & Informat Syst, Birkbeck, London, England
[3] Univ Warwick, Math Inst, Coventry CV4 7AL, W Midlands, England
来源：
GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE | 2016年 / 9224卷
基金：
英国工程与自然科学研究理事会;
关键词：
INDUCED SUBGRAPHS; GRAPHS;
D O I：
10.1007/978-3-662-53174-7_25
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We present a hereditary class of graphs of unbounded clique-width which is well-quasi-ordered by the induced subgraph relation. This result provides the negative answer to a question asked by Daligault, Rao and Thomasse in [3].
引用
收藏
页码：351 / 359
页数：9
相关论文
共 15 条
  • [1] Well-quasi-ordering versus clique-width
    Lozin, Vadim
    Razgon, Igor
    Zamaraev, Viktor
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2018, 130 : 1 - 18
  • [2] Clique-Width and Well-Quasi-Ordering of Triangle-Free Graph Classes
    Dabrowski, Konrad K.
    Lozin, Vadim V.
    Paulusma, Daniel
    GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE (WG 2017), 2017, 10520 : 220 - 233
  • [3] Well-Quasi-Ordering versus Clique-Width: New Results on Bigenic Classes
    Dabrowski, Konrad K.
    Lozin, Vadim V.
    Paulusma, Daniel
    Combinatorial Algorithms, 2016, 9843 : 253 - 265
  • [4] Clique-width and well-quasi-ordering of triangle-free graph classes
    Dabrowski, Konrad K.
    Lozin, Vadim V.
    Paulusma, Daniel
    JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2020, 108 (108) : 64 - 91
  • [5] Well-Quasi-Ordering versus Clique-Width: New Results on Bigenic Classes
    Dabrowski, Konrad K.
    Lozin, Vadim V.
    Paulusma, Daniel
    ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS, 2018, 35 (02): : 253 - 274
  • [6] Branch-width and well-quasi-ordering in matroids and graphs
    Geelen, JF
    Gerards, AMH
    Whittle, G
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2002, 84 (02) : 270 - 290
  • [7] Induced minors and well-quasi-ordering
    Blasiok, Jaroslaw
    Kaminski, Marcin
    Raymond, Jean-Florent
    Trunck, Theophile
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2019, 134 : 110 - 142
  • [8] Reasoning in Argumentation Frameworks of Bounded Clique-Width
    Dvorak, Wolfgang
    Szeider, Stefan
    Woltran, Stefan
    COMPUTATIONAL MODELS OF ARGUMENT: PROCEEDINGS OF COMMA 2010, 2010, 216 : 219 - 230
  • [9] Well-quasi-ordering and Embeddability of Relational Structures
    Pouzet, Maurice
    ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS, 2024, 41 (01): : 183 - 278
  • [10] Parity Games of Bounded Tree- and Clique-Width
    Ganardi, Moses
    FOUNDATIONS OF SOFTWARE SCIENCE AND COMPUTATION STRUCTURES (FOSSACS 2015), 2015, 9034 : 390 - 404
12