Linear Clique-Width for Subclasses of Cographs, With Connections to Permutations
Robert Brignall, Nicholas Korpelainen, Vincent R. Vatter · arXiv (Cornell University) · 2013
We prove that a hereditary property of cographs has bounded linear cliquewidth 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, and the similarities between these two strands of investigation lead us to a conjecture relating the graph properties of bounded linear clique-width to permutation classes with rational generating functions which would have far-reaching consequences if true.