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

Brignall, Robert and Cocks, Daniel (2023). A framework for minimal hereditary classes of graphs of unbounded clique-width. SIAM Journal on Discrete Mathematics, 37(4) pp. 2558–2584.

DOI: https://doi.org/10.1137/22M1487448

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 a large family of minimal hereditary classes of graphs of unbounded clique-width, some previously identified 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.

Viewing alternatives

Look up in Google Scholar

Download history

Metrics

Public Attention

Altmetrics from Altmetric

Number of Citations

Citations from Dimensions

Item Actions

Export

About

CORE (COnnecting REpositories)