Dabrowski, K.K. and Lozin , V.V. and Paulusma , D. (2020) 'Clique-width and well-quasi ordering of triangle-free graph classes.', Journal of computer and system sciences., 108 . pp. 64-91.
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.
| Item Type: | Article |
|---|---|
| Full text: | Publisher-imposed embargo (AM) Accepted Manuscript Available under License - Creative Commons Attribution. File format - PDF (655Kb) |
| Full text: | (VoR) Version of Record Available under License - Creative Commons Attribution. Download PDF (861Kb) |
| Status: | Peer-reviewed |
| Publisher Web site: | https://doi.org/10.1016/j.jcss.2019.09.001 |
| Publisher 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/) |
| Date accepted: | 09 September 2019 |
| Date deposited: | 10 September 2019 |
| Date of first online publication: | 26 September 2019 |
| Date first made open access: | 15 November 2019 |
Save or Share this output
| Export: | |
| Look up in GoogleScholar |
