Uncountably Many Minimal Hereditary Classes of Graphs of Unbounded Clique-Width

Brignall, Robert and Cocks, Daniel (2022). Uncountably Many Minimal Hereditary Classes of Graphs of Unbounded Clique-Width. Electronic Journal of Combinatorics, 29(1), article no. P1.63.

DOI: https://doi.org/10.37236/10483

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 not almost periodic.