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

DOI10.1137/22m1487448zbMath1526.05118arXiv2203.15446MaRDI QIDQ6069433

Daniel G. Cocks, Robert Brignall

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-widthlinear clique-widthhereditary graph classes

Mathematics Subject Classification ID

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

Cites Work

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

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