K.K. Dabrowski
Clique-width and well-quasi ordering of triangle-free graph classes
Dabrowski, K.K.; Lozin, V.V.; Paulusma, D.
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 |
Files
Published Journal Article
(881 Kb)
PDF
Publisher Licence URL
http://creativecommons.org/licenses/by/4.0/
Copyright Statement
© 2019 The Authors. Published by Elsevier Ltd. This is an open access article under the CC BY license. (http://creativecommons.org/licenses/by/4.0/)
You might also like
Clique‐width: Harnessing the power of atoms
(2023)
Journal Article
Finding Matching Cuts in H-Free Graphs
(2023)
Journal Article
The Complexity of L(p, q)-Edge-Labelling
(2023)
Journal Article
Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs
(2023)
Journal Article
Computing balanced solutions for large international kidney exchange schemes
(2022)
Conference Proceeding