Characterisation of minimal hereditary graph classes of unbounded clique-width

Let Gδ\mathcal{G}^\delta be the hereditary graph class associated with the sequence δ\delta, and let Δmin\Delta_{\min} denote the set of sequences satisfying the defining minimality conditions, including recurrence, bounded clique-width for gap factors, and bounded Mβ\mathcal{M}^\beta for the bond set β\beta.

Characterisation conjecture. The hereditary graph class Gδ\mathcal{G}^\delta is minimal of unbounded clique-width if and only if δΔmin\delta \in \Delta_{\min}.

The sufficient conditions for membership in Δmin\Delta_{\min} are known to yield minimal hereditary classes of unbounded clique-width, and recurrence together with bounded clique-width for gap factors is necessary. The unresolved part is whether the bond set must also have bounded Mβ\mathcal{M}^\beta; no counterexample with δΔmin\delta \notin \Delta_{\min} is known.

Sources & referencesView supporting material

Primary source

Robert Brignall and Daniel Cocks, “A framework for minimal hereditary classes of graphs of unbounded clique-width”, arXiv:2203.15446 (2023).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.