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