Well-quasi-ordering versus clique-width: new results on bigenic classes

Dabrowski, K.K.; Lozin, V.V.; Paulusma, D.

doi:10.1007/s11083-017-9430-7

Well-quasi-ordering versus clique-width: new results on bigenic classes

Dabrowski, K.K.; Lozin, V.V.; Paulusma, D.

Authors

K.K. Dabrowski

V.V. Lozin

Professor Daniel Paulusma daniel.paulusma@durham.ac.uk
Professor

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 P4. 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.

Citation

Dabrowski, K., Lozin, V., & Paulusma, D. (2018). Well-quasi-ordering versus clique-width: new results on bigenic classes. Order, 35(2), 253-274. https://doi.org/10.1007/s11083-017-9430-7

Journal Article Type	Article
Acceptance Date	May 13, 2017
Online Publication Date	Jun 29, 2017
Publication Date	Jul 1, 2018
Deposit Date	May 20, 2017
Publicly Available Date	May 23, 2017
Journal	Order
Print ISSN	0167-8094
Electronic ISSN	1572-9273
Publisher	Springer
Peer Reviewed	Peer Reviewed
Volume	35
Issue	2
Pages	253-274
DOI	https://doi.org/10.1007/s11083-017-9430-7
Public URL	https://durham-repository.worktribe.com/output/1357922

Files

Accepted Journal Article (483 Kb)
PDF

Publisher Licence URL
http://creativecommons.org/licenses/by/4.0/

Copyright Statement
© The Author(s) 2017 Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.