Uncountably many minimal hereditary classes of graphs of unbounded clique-width (Q2121810): Difference between revisions

Summary: 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 \textit{A. Collins} et al. [Discrete Appl. Math. 248, 145--152 (2018; Zbl 1395.05051)]. Finally, we show that the other direction of the conjecture is false, since \(\Gamma\) also contains words that are not almost periodic.