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.
|
Text
versus_submission_rev.pdf - Author Accepted Manuscript Download (300kB) | Preview |
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.
| 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 |
Dimensions
Dimensions
