The Open UniversitySkip to content

Linear Clique-Width for Hereditary Classes of Cographs

Brignall, Robert; Korpelainen, Nicholas and Vatter, Vincent (2017). Linear Clique-Width for Hereditary Classes of Cographs. Journal of Graph Theory, 84(4) pp. 501–511.

Full text available as:
PDF (Accepted Manuscript) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
Download (167kB) | Preview
DOI (Digital Object Identifier) Link:
Google Scholar: Look up in Google Scholar


The class of cographs is known to have unbounded linear clique-width. We prove that a hereditary class of cographs has bounded linear clique-width if and only if it does not contain all quasi-threshold graphs or their complements. The proof borrows ideas from the enumeration of permutation classes.

Item Type: Journal Item
Copyright Holders: 2016 Wiley Periodicals, Inc.
ISSN: 0364-9024
Project Funding Details:
Funded Project NameProject IDFunding Body
Infinite Antichains: from Permutations to Combinatorial Structures (XM-11-009-RB)EP/J006130/1EPSRC (Engineering and Physical Sciences Research Council)
Keywords: linear clique-width; cographs; threshold graphs; quasi-threshold graphs; clique-width
Academic Unit/School: Faculty of Science, Technology, Engineering and Mathematics (STEM) > Mathematics and Statistics
Faculty of Science, Technology, Engineering and Mathematics (STEM)
Item ID: 48647
Depositing User: Robert Brignall
Date Deposited: 20 Feb 2017 15:11
Last Modified: 01 May 2019 11:37
Share this page:


Altmetrics from Altmetric

Citations from Dimensions

Download history for this item

These details should be considered as only a guide to the number of downloads performed manually. Algorithmic methods have been applied in an attempt to remove automated downloads from the displayed statistics but no guarantee can be made as to the accuracy of the figures.

Actions (login may be required)

Policies | Disclaimer

© The Open University   contact the OU