Uncountably many minimal hereditary classes of graphs of unbounded clique-width

Abstract

Given an infinite word over the alphabet $\{0,1,2,3\}$, we define a class of bipartite hereditary graphs ${\mathcal{G}}^{\alpha }$, and show that ${\mathcal{G}}^{\alpha }$ has unbounded clique-width unless $\alpha$ contains at most finitely many non-zero letters. We also show that ${\mathcal{G}}^{\alpha }$ is minimal of unbounded clique-width if and only if $\alpha$ belongs to a precisely defined collection of words $\Gamma$. The set $\Gamma$ includes all almost periodic words containing at least one non-zero letter, which both enables us to exhibit uncountably many pairwise distinct minimal classes of unbounded clique width, and also proves one direction of a conjecture due to Collins, Foniok, Korpelainen, Lozin and Zamaraev. Finally, we show that the other direction of the conjecture is false, since $\Gamma$ also contains words that are \emph{not} almost periodic.

References in corpus (3)

• Clique-Width for Hereditary Graph Classes
• The grid theorem for vertex-minors
• Minimal classes of graphs of unbounded clique-width defined by finitely many forbidden induced subgraphs

Cited by in corpus (3)

• A framework for minimal hereditary classes of graphs of unbounded clique-width
• MSO Undecidability for Hereditary Classes of Unbounded Clique-Width
• $t$-sails and sparse hereditary classes of unbounded tree-width