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.

DOI: https://doi.org/10.1002/jgt.22037

Abstract

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.

Viewing alternatives

Metrics

Item Actions

Export

You can export this page using these formats Digital Object Identifier - DOI

About

• Item ORO ID
• 48647
• Item Type
• Journal Item
• ISSN
• 0364-9024
• Project Funding Details

• Funded Project Name	Project ID	Funding Body
  Infinite Antichains: from Permutations to Combinatorial Structures (XM-11-009-RB)	EP/J006130/1	EPSRC (Engineering and Physical Sciences Research Council)

• Keywords
• linear clique-width; cographs; threshold graphs; quasi-threshold graphs; clique-width
• Academic Unit or School
• Faculty of Science, Technology, Engineering and Mathematics (STEM) > Mathematics and Statistics
  Faculty of Science, Technology, Engineering and Mathematics (STEM)
• Copyright Holders
• © 2016 Wiley Periodicals, Inc.
• Depositing User
• Robert Brignall