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. (2016) 'Well-quasi-ordering versus clique-width : new results on bigenic classes.', in Combinatorial algorithms : 27th international workshop, IWOCA 2016, Helsinki, Finland, August 17-19, 2016 ; proceedings. Cham, Switzerland: Springer, pp. 253-265. Lecture notes in computer science. (9843).


Daligault, Rao and Thomassé conjectured that if a hereditary class of graphs is well-quasi-ordered by the induced subgraph relation then it has bounded clique-width. Lozin, Razgon and Zamaraev recently showed that this conjecture is not true for infinitely defined classes. For finitely defined classes the conjecture is still open. It 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 P4P4. For bigenic classes of graphs i.e. ones defined by two forbidden induced subgraphs there are several open cases in both classifications. We reduce the number of open cases for well-quasi-orderability of such classes from 12 to 9. Our results agree with the conjecture and imply that there are only two remaining cases to verify for bigenic classes.

Item Type:Book chapter
Full text:(AM) Accepted Manuscript
Download PDF
Publisher Web site:
Publisher statement:The final publication is available at Springer via
Date accepted:15 July 2016
Date deposited:03 October 2016
Date of first online publication:09 August 2016
Date first made open access:09 August 2017

Save or Share this output

Look up in GoogleScholar