Well-quasi-ordering versus clique-width

Lozin, Vadim, Razgon, Igor and Zamaraev, Viktor ORCID: 0000-0001-5755-4141
(2018) Well-quasi-ordering versus clique-width. JOURNAL OF COMBINATORIAL THEORY SERIES B, 130. pp. 1-18.

[img] Text
versus_submission_rev.pdf - Author Accepted Manuscript

Download (300kB) | Preview


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.

Item Type: Article
Uncontrolled Keywords: Well-quasi-ordering, Induced subgraphs, Clique-width, Hereditary classes
Depositing User: Symplectic Admin
Date Deposited: 29 Oct 2019 09:49
Last Modified: 19 Jan 2023 00:21
DOI: 10.1016/j.jctb.2017.09.012
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3059777