Publication detailsDabrowski, K.K., Lozin, V.V. & Paulusma, D. (2017), Clique-width and well-quasi ordering of triangle-free graph classes, in Bodlaender, Hans L. & Woeginger, Gerhard J. eds, Lecture Notes in Computer Science 10520: WG 2017: 43rd International Workshop on Graph-Theoretic Concepts in Computer Science. Eindhoven, The Netherlands, Springer, Cham, 220-233.
- Publication type: Conference Paper
- ISSN/ISBN: 9783319687049, 9783319687056, 0302-9743, 1611-3349
- DOI: 10.1007/978-3-319-68705-6_17
- Further publication details on publisher web site
- Durham Research Online (DRO) - may include full text
Author(s) from Durham
Daligault, Rao and Thomassé asked whether every hereditary graph class that is well-quasi-ordered by the induced subgraph relation has bounded clique-width. Lozin, Razgon and Zamaraev (WG 2015) gave a negative answer to this question, but their counterexample is a class that can only be characterised by infinitely many forbidden induced subgraphs. This raises the issue of whether their question has a positive answer for finitely defined hereditary graph classes. Apart from two stubborn cases, this has been confirmed when at most two induced subgraphs H1,H2H1,H2 are forbidden. We confirm it for one of the two stubborn cases, namely for the case (H1,H2)=(triangle,P2+P4)(H1,H2)=(triangle,P2+P4) by proving that the class of (triangle,P2+P4)(triangle,P2+P4) -free graphs has bounded clique-width and is well-quasi-ordered. Our technique is based on a special decomposition of 3-partite graphs. We also use this technique to completely determine which classes of (triangle,H)(triangle,H) -free graphs are well-quasi-ordered.