Linear Clique-Width for Hereditary Classes of Cographs
classification
🧮 math.CO
keywords
clique-widthcographslinearclassclasseshereditaryborrowsbounded
read the original 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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.