Linear Clique-Width for Hereditary Classes of Cographs

2013/05/03 by Brignall, Robert, Korpelainen, Nicholas, Vatter, Vincent
#05C75 #05C78 #05C85 #68R10 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1305.0636

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.

Related

• Clique-width of unit interval graphs
• Infinitely many minimal classes of graphs of unbounded clique-width
• Clique-Width for Graph Classes Closed under Complementation
• Clique-width and Well-Quasi-Ordering of Triangle-Free Graph Classes
• Clique-width of Graph Classes Defined by Two Forbidden Induced Subgraphs