K. K. Dabrowski
Well-quasi-ordering versus clique-width: new results on bigenic classes
Dabrowski, K. K.; Lozin, V. V.; Paulusma, D.
Authors
Contributors
Veli Mäkinen
Editor
Simon J. Puglisi
Editor
Leena Salmela
Editor
Abstract
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.
Citation
Dabrowski, K. K., Lozin, V. V., & Paulusma, D. (2016, August). Well-quasi-ordering versus clique-width: new results on bigenic classes. Presented at 27th International Workshop on Combinatorial Algorithms (IWOCA 2016)., Helsinki, Finland
Presentation Conference Type | Conference Paper (Published) |
---|---|
Conference Name | 27th International Workshop on Combinatorial Algorithms (IWOCA 2016). |
Start Date | Aug 17, 2016 |
End Date | Aug 19, 2016 |
Acceptance Date | Jul 15, 2016 |
Online Publication Date | Aug 9, 2016 |
Publication Date | Aug 9, 2016 |
Deposit Date | Oct 1, 2016 |
Publicly Available Date | Aug 9, 2017 |
Print ISSN | 0302-9743 |
Pages | 253-265 |
Series Title | Lecture notes in computer science |
Series Number | 9843 |
Series ISSN | 0302-9743,1611-3349 |
Book Title | Combinatorial algorithms : 27th international workshop, IWOCA 2016, Helsinki, Finland, August 17-19, 2016 ; proceedings. |
ISBN | 9783319445427 |
DOI | https://doi.org/10.1007/978-3-319-44543-4_20 |
Public URL | https://durham-repository.worktribe.com/output/1149949 |
Files
Accepted Conference Proceeding
(391 Kb)
PDF
Copyright Statement
The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-319-44543-4_20
You might also like
Clique‐width: Harnessing the power of atoms
(2023)
Journal Article
Solving Infinite-Domain CSPs Using the Patchwork Property
(2023)
Presentation / Conference Contribution
Disjunctive Temporal Problems under Structural Restrictions
(2021)
Presentation / Conference Contribution
Fine-Grained Complexity of Temporal Problems
(2020)
Presentation / Conference Contribution
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