We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

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

Dabrowski, K.K. and Lozin, V.V. and Paulusma, D. (2018) 'Well-quasi-ordering versus clique-width : new results on bigenic classes.', Order., 35 (2). pp. 253-274.


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.

Item Type:Article
Full text:(AM) Accepted Manuscript
Available under License - Creative Commons Attribution.
Download PDF
Full text:(VoR) Version of Record
Available under License - Creative Commons Attribution.
Download PDF (Advance online version)
Publisher Web site:
Publisher statement:© The Author(s) 2017 Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (, 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.
Date accepted:13 May 2017
Date deposited:23 May 2017
Date of first online publication:29 June 2017
Date first made open access:No date available

Save or Share this output

Look up in GoogleScholar