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
• Electronic ISSN: 1090-2724
• 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