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.
@article{10_37236_10483,
author = {Robert Brignall and Daniel Cocks},
title = {Uncountably many minimal hereditary classes of graphs of unbounded clique-width},
journal = {The electronic journal of combinatorics},
year = {2022},
volume = {29},
number = {1},
doi = {10.37236/10483},
zbl = {1486.05258},
url = {http://geodesic.mathdoc.fr/articles/10.37236/10483/}
}
TY - JOUR
AU - Robert Brignall
AU - Daniel Cocks
TI - Uncountably many minimal hereditary classes of graphs of unbounded clique-width
JO - The electronic journal of combinatorics
PY - 2022
VL - 29
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/10483/
DO - 10.37236/10483
ID - 10_37236_10483
ER -
%0 Journal Article
%A Robert Brignall
%A Daniel Cocks
%T Uncountably many minimal hereditary classes of graphs of unbounded clique-width
%J The electronic journal of combinatorics
%D 2022
%V 29
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/10483/
%R 10.37236/10483
%F 10_37236_10483
Robert Brignall; Daniel Cocks. Uncountably many minimal hereditary classes of graphs of unbounded clique-width. The electronic journal of combinatorics, Tome 29 (2022) no. 1. doi: 10.37236/10483
