The Library
Well-quasi-ordering versus clique-width : new results on bigenic classes
Tools
Dabrowski, Konrad K., Lozin, Vadim V. and Paulusma, Daniel (2018) Well-quasi-ordering versus clique-width : new results on bigenic classes. Order, 35 . pp. 253-274. doi:10.1007/s11083-017-9430-7 ISSN 0167-8094.
|
PDF
WRAP-well-quasi-ordering-versus-clique-Lozin-2017.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (1017Kb) | Preview |
|
PDF
ORDE-D-16-00085.pdf - Accepted Version Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer. Download (471Kb) |
Official URL: https://doi.org/10.1007/s11083-017-9430-7
Abstract
Daligault, Rao and Thomassé asked whether a hereditary class of graphs well-quasi-ordered by the induced subgraph relation has bounded clique-width. Lozin, Razgon and Zamaraev recently showed that this is not true for classes defined by infinitely many forbidden induced subgraphs. However, in the case of finitely many forbidden induced subgraphs the question remains open and we conjecture that in this case the answer is positive. The conjecture is known to hold for classes of graphs defined by a single forbidden induced subgraph H, as such graphs are well-quasi-ordered and are of bounded clique-width if and only if H is an induced subgraph of P 4. For bigenic classes of graphs, i.e. ones defined by two forbidden induced subgraphs, there are several open cases in both classifications. In the present paper we obtain a number of new results on well-quasi-orderability of bigenic classes, each of which supports the conjecture.
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: | Order | ||||||||||||
Publisher: | Springer | ||||||||||||
ISSN: | 0167-8094 | ||||||||||||
Official Date: | July 2018 | ||||||||||||
Dates: |
|
||||||||||||
Volume: | 35 | ||||||||||||
Page Range: | pp. 253-274 | ||||||||||||
DOI: | 10.1007/s11083-017-9430-7 | ||||||||||||
Status: | Peer Reviewed | ||||||||||||
Publication Status: | Published | ||||||||||||
Access rights to Published version: | Open Access (Creative Commons) | ||||||||||||
Date of first compliant deposit: | 18 May 2017 | ||||||||||||
Date of first compliant Open Access: | 18 January 2018 | ||||||||||||
RIOXX Funder/Project Grant: |
|
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year