Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
8903856 | Journal of Combinatorial Theory, Series B | 2018 | 18 Pages |
Abstract
Does well-quasi-ordering by induced subgraphs imply bounded clique-width for hereditary classes? This question was asked by Daligault, Rao, and Thomassé [7]. We answer this question negatively by presenting a hereditary class of graphs of unbounded clique-width which is well-quasi-ordered by the induced subgraph relation. We also show that graphs in our class have at most logarithmic clique-width and that the number of minimal forbidden induced subgraphs for our class is infinite. These results lead to a conjecture relaxing the above question and to a number of related open questions connecting well-quasi-ordering and clique-width.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Vadim Lozin, Igor Razgon, Viktor Zamaraev,