The Library
Clique-width and Well-Quasi-Ordering of Triangle-Free graph classes
Tools
Dabrowski, Konrad K., Lozin, Vadim V. and Paulusma, Daniël (2020) Clique-width and Well-Quasi-Ordering of Triangle-Free graph classes. Journal of Computer and System Sciences, 108 . pp. 64-91. doi:10.1016/j.jcss.2019.09.001 ISSN 0022-0000.
|
PDF
WRAP-clique-width-well-quasi-ordering-triangle-free-Lozin-2019.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (1583Kb) | Preview |
|
PDF
JCSS.pdf - Accepted Version Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer. Download (654Kb) |
Official URL: https://doi.org/10.1016/j.jcss.2019.09.001
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: | Journal Article | ||||||||
---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||||||
Journal or Publication Title: | Journal of Computer and System Sciences | ||||||||
Publisher: | Academic Press | ||||||||
ISSN: | 0022-0000 | ||||||||
Official Date: | March 2020 | ||||||||
Dates: |
|
||||||||
Volume: | 108 | ||||||||
Page Range: | pp. 64-91 | ||||||||
DOI: | 10.1016/j.jcss.2019.09.001 | ||||||||
Status: | Peer Reviewed | ||||||||
Publication Status: | Published | ||||||||
Access rights to Published version: | Open Access (Creative Commons) | ||||||||
Date of first compliant deposit: | 3 October 2019 | ||||||||
Date of first compliant Open Access: | 3 October 2019 |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year