K. K. Dabrowski
Clique-width and well-quasi ordering of triangle-free graph classes
Dabrowski, K. K.; Lozin, V. V.; Paulusma, D.
Authors
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
Accepted Conference Proceeding
(460 Kb)
PDF
Copyright Statement
The final publication is available at Springer via https://doi.org/10.1007/978-3-319-68705-6_17.
You might also like
Solving Infinite-Domain CSPs Using the Patchwork Property
(2023)
Conference Proceeding
Disjunctive Temporal Problems under Structural Restrictions
(2021)
Conference Proceeding
Fine-Grained Complexity of Temporal Problems
(2020)
Conference Proceeding
Independent transversals versus transversals
(2019)
Conference Proceeding
Filling the complexity gaps for colouring planar and bounded degree graphs
(2019)
Journal Article
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search