A framework for minimal hereditary classes of graphs of unbounded clique-width

Abstract

We create a framework for hereditary graph classes ${\mathcal{G}}^{\delta }$ built on a two-dimensional grid of vertices and edge sets defined by a triple $\delta =\{\alpha ,\beta ,\gamma \}$ of objects that define edges between consecutive columns, edges between non-consecutive columns (called bonds), and edges within columns. This framework captures all previously proven minimal hereditary classes of graph of unbounded clique-width, and many new ones, although we do not claim this includes all such classes. We show that a graph class ${\mathcal{G}}^{\delta }$ has unbounded clique-width if and only if a certain parameter ${\mathcal{N}}^{\delta }$ is unbounded. We further show that ${\mathcal{G}}^{\delta }$ is minimal of unbounded clique-width (and, indeed, minimal of unbounded linear clique-width) if another parameter ${\mathcal{M}}^{\beta }$ is bounded, and also $\delta$ has defined recurrence characteristics. Both the parameters ${\mathcal{N}}^{\delta }$ and ${\mathcal{M}}^{\beta }$ are properties of a triple $\delta =(\alpha ,\beta ,\gamma )$, and measure the number of distinct neighbourhoods in certain auxiliary graphs. Throughout our work, we introduce new methods to the study of clique-width, including the use of Ramsey theory in arguments related to unboundedness, and explicit (linear) clique-width expressions for subclasses of minimal classes of unbounded clique-width.

33 pages, 7 figures

References in corpus (3)

• The grid theorem for vertex-minors
• Minimal classes of graphs of unbounded clique-width defined by finitely many forbidden induced subgraphs
• Uncountably many minimal hereditary classes of graphs of unbounded clique-width

Cited by in corpus (1)

• $t$-sails and sparse hereditary classes of unbounded tree-width