A Framework for Minimal Hereditary Classes of Graphs of Unbounded Clique-Width

DOI10.1137/22M1487448MaRDI QIDQ6069433zbMATH OpenFDO

Authors Robert Brignall, Daniel G. Cocks

Publication date 14 November 2023

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2203.15446

zbMATH Keywords

clique-widthhereditary graph classeslinear clique-width

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85)

Abstract: We create a framework for hereditary graph classes $mathcal{G}^{d}elta$ built on a two-dimensional grid of vertices and edge sets defined by a triple $$ 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}^{d}elta$ has unbounded clique-width if and only if a certain parameter $mathcal{N}^{d}elta$ is unbounded. We further show that $mathcal{G}^{d}elta$ is minimal of unbounded clique-width (and, indeed, minimal of unbounded linear clique-width) if another parameter $$ is bounded, and also $delta$ has defined recurrence characteristics. Both the parameters $mathcal{N}^{d}elta$ and $$ are properties of a triple $$, 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.

Recommendations

• Infinitely many minimal classes of graphs of unbounded clique-width
• Uncountably many minimal hereditary classes of graphs of unbounded clique-width
• Minimal classes of graphs of unbounded clique-width defined by finitely many forbidden induced subgraphs
• Clique-width and the speed of hereditary properties
• A new graph construction of unbounded clique-width

Cites work

• Between clique-width and linear clique-width of bipartite graphs
• Graph minors. V. Excluding a planar graph
• Graph theory
• Handle-rewriting hypergraph grammars
• Infinitely many minimal classes of graphs of unbounded clique-width
• Linear clique-width for hereditary classes of cographs
• Linear time solvable optimization problems on graphs of bounded clique-width
• Minimal classes of graphs of unbounded clique-width
• Minimal classes of graphs of unbounded clique-width defined by finitely many forbidden induced subgraphs
• The grid theorem for vertex-minors
• Uncountably many minimal hereditary classes of graphs of unbounded clique-width

Cited in

(3)

• Bounding the mim‐width of hereditary graph classes
• \(t\)-sails and sparse hereditary classes of unbounded tree-width
• An overview of universal obstructions for graph parameters

This page was built for publication: A Framework for Minimal Hereditary Classes of Graphs of Unbounded Clique-Width

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6069433)