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



Abstract

We obtain a complete classification of graphs H for which the class of -free graphs is well-quasi-ordered by the induced subgraph relation and an almost complete classification of graphs H for which the class of -free graphs has bounded clique-width. In particular, we show that for these graph classes, well-quasi-orderability implies boundedness of clique-width. To obtain our results, we further refine a known method based on canonical decomposition. This leads to a new decomposition technique that is applicable to both notions, well-quasi-orderability and clique-width.

Citation

Dabrowski, K., Lozin, V., & Paulusma, D. (2020). Clique-width and well-quasi ordering of triangle-free graph classes. Journal of Computer and System Sciences, 108, 64-91. https://doi.org/10.1016/j.jcss.2019.09.001

Journal Article Type Article
Acceptance Date Sep 9, 2019
Online Publication Date Sep 26, 2019
Publication Date Mar 31, 2020
Deposit Date Sep 10, 2019
Publicly Available Date Nov 15, 2019
Journal Journal of Computer and System Sciences
Print ISSN 0022-0000
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 108
Pages 64-91
DOI https://doi.org/10.1016/j.jcss.2019.09.001
Public URL https://durham-repository.worktribe.com/output/1292820

Files






You might also like



Downloadable Citations