
The Library
Well-quasi-ordering versus clique-width
Tools
Lozin, Vadim V., Razgon, Igor and Zamaraev, Viktor (2018) Well-quasi-ordering versus clique-width. Journal of Combinatorial Theory, Series B, 130 . pp. 1-18. doi:10.1016/j.jctb.2017.09.012 ISSN 0095-8956.
|
PDF
WRAP-well-quasi-ordering-versus-clique-width-Lozin-2017.pdf - Accepted Version - Requires a PDF viewer. Download (627Kb) | Preview |
Official URL: http://dx.doi.org/10.1016/j.jctb.2017.09.012
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: | Journal Article | ||||||||
---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||||||
Library of Congress Subject Headings (LCSH): | Graph theory | ||||||||
Journal or Publication Title: | Journal of Combinatorial Theory, Series B | ||||||||
Publisher: | Academic Press | ||||||||
ISSN: | 0095-8956 | ||||||||
Official Date: | May 2018 | ||||||||
Dates: |
|
||||||||
Volume: | 130 | ||||||||
Page Range: | pp. 1-18 | ||||||||
DOI: | 10.1016/j.jctb.2017.09.012 | ||||||||
Status: | Peer Reviewed | ||||||||
Publication Status: | Published | ||||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||||
Date of first compliant deposit: | 9 October 2017 | ||||||||
Date of first compliant Open Access: | 2 October 2018 | ||||||||
Funder: | Engineering and Physical Sciences Research Council (EPSRC) | ||||||||
Grant number: | EP/L020408/1 |
Request changes or add full text files to a record
Repository staff actions (login required)
![]() |
View Item |
Downloads
Downloads per month over past year