Clique-width and well-quasi ordering of triangle-free graph classes

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

Abstract

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.

Citation

Dabrowski, K. K., Lozin, V. V., & Paulusma, D. (2017, June). Clique-width and well-quasi ordering of triangle-free graph classes. Presented at WG 2017: 43rd International Workshop on Graph-Theoretic Concepts in Computer Science, Eindhoven, The Netherlands

• Presentation Conference Type: Conference Paper (published)
• Conference Name: WG 2017: 43rd International Workshop on Graph-Theoretic Concepts in Computer Science
• Start Date: Jun 21, 2017
• End Date: Jun 23, 2017
• Acceptance Date: Jul 31, 2017
• Online Publication Date: Nov 2, 2017
• Publication Date: Nov 2, 2017
• Deposit Date: May 31, 2017
• Publicly Available Date: Nov 2, 2018
• Print ISSN: 0302-9743
• Pages: 220-233
• Series Title: Lecture notes in computer science
• Series Number: 10520
• Series ISSN: 0302-9743,1611-3349
• Book Title: Graph-Theoretic Concepts in Computer Science : 43rd International Workshop, WG 2017, Eindhoven, The Netherlands, June 21-23, 2017. Revised selected papers.
• ISBN: 9783319687049
• DOI: https://doi.org/10.1007/978-3-319-68705-6_17
• Public URL: https://durham-repository.worktribe.com/output/1147195