Skip to main content

Research Repository

Advanced Search

Well-quasi-ordering versus clique-width: new results on bigenic classes

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

Well-quasi-ordering versus clique-width: new results on bigenic classes Thumbnail


Authors

K. K. Dabrowski

V. V. Lozin



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). Well-quasi-ordering versus clique-width: new results on bigenic classes. In V. Mäkinen, S. J. Puglisi, & L. Salmela (Eds.), Combinatorial algorithms : 27th international workshop, IWOCA 2016, Helsinki, Finland, August 17-19, 2016 ; proceedings (253-265). https://doi.org/10.1007/978-3-319-44543-4_20

Conference Name 27th International Workshop on Combinatorial Algorithms (IWOCA 2016).
Conference Location Helsinki, Finland
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 Mar 29, 2024
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





You might also like



Downloadable Citations