Skip to main content

Research Repository

Advanced Search

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

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

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


Authors

K. K. Dabrowski

V. V. Lozin



Contributors

Hans L. Bodlaender
Editor

Gerhard J. Woeginger
Editor

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). Clique-width and well-quasi ordering of triangle-free graph classes. In H. L. Bodlaender, & G. J. Woeginger (Eds.), Graph-Theoretic Concepts in Computer Science : 43rd International Workshop, WG 2017, Eindhoven, The Netherlands, June 21-23, 2017. Revised selected papers (220-233). https://doi.org/10.1007/978-3-319-68705-6_17

Conference Name WG 2017: 43rd International Workshop on Graph-Theoretic Concepts in Computer Science
Conference Location Eindhoven, The Netherlands
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 Mar 28, 2024
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

Files





You might also like



Downloadable Citations