Publication detailsDabrowski, K.K., Lozin, V.V. & Paulusma, D. (2020). Clique-width and well-quasi ordering of triangle-free graph classes. Journal of Computer and System Sciences 108: 64-91.
- Publication type: Journal Article
- ISSN/ISBN: 0022-0000
- DOI: 10.1016/j.jcss.2019.09.001
- Further publication details on publisher web site
- Durham Research Online (DRO) - may include full text
Author(s) from Durham
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.