# 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.

## Abstract

Given an infinite word over the alphabet , we define a class of bipartite hereditary graphs , and show that has unbounded clique-width unless contains at most finitely many non-zero letters.

We also show that is minimal of unbounded clique-width if and only if belongs to a precisely defined collection of words . The set 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 also contains words that are not almost periodic.

## Metrics

### Public Attention

Altmetrics from Altmetric

### Number of Citations

Citations from Dimensions