Cookies

We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.


Durham Research Online
You are in:

Clique-width and well-quasi ordering of triangle-free graph classes.

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:
Export
Look up in GoogleScholar