Infinitely many minimal classes of graphs of unbounded clique-width

DOI10.1016/J.DAM.2017.02.012MaRDI QIDQ2413975zbMATH OpenOpenAlexFDO

Authors Andrew Collins, Jan Foniok, Nicholas Korpelainen, Vadim Lozin, Victor Zamaraev

Publication date 17 September 2018

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1701.08857, http://wrap.warwick.ac.uk/86094/7/WRAP-infinitely-many-minimal-classes-graphs-unbounded-Lozin-2017.pdf

zbMATH Keywords

clique-widthhereditary classlinear clique-width

Mathematics Subject Classification ID

Distance in graphs (05C12) Graph minors (05C83)

Abstract: The celebrated theorem of Robertson and Seymour states that in the family of minor-closed graph classes, there is a unique minimal class of graphs of unbounded tree-width, namely, the class of planar graphs. In the case of tree-width, the restriction to minor-closed classes is justified by the fact that the tree-width of a graph is never smaller than the tree-width of any of its minors. This, however, is not the case with respect to clique-width, as the clique-width of a graph can be (much) smaller than the clique-width of its minor. On the other hand, the clique-width of a graph is never smaller than the clique-width of any of its induced subgraphs, which allows us to be restricted to hereditary classes (that is, classes closed under taking induced subgraphs), when we study clique-width. Up to date, only finitely many minimal hereditary classes of graphs of unbounded clique-width have been discovered in the literature. In the present paper, we prove that the family of such classes is infinite. Moreover, we show that the same is true with respect to linear clique-width.

Recommendations

• 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
• Linear clique-width for hereditary classes of cographs
• Well-quasi-ordering versus clique-width
• Clique-width and the speed of hereditary properties

Cites work

• Approximating clique-width and branch-width
• Graph minors. V. Excluding a planar graph
• Graph minors. XX: Wagner's conjecture
• Handle-rewriting hypergraph grammars
• scientific article; zbMATH DE number 2191997 (Why is no real title available?)
• 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
• On canonical antichains
• Rank-width and vertex-minors
• Upper bounds to the clique width of graphs
• Well-quasi-order of relabel functions
• Well-quasi-ordering does not imply bounded clique-width

Cited in

(12)

• Clique-width and the speed of hereditary properties
• 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
• Minimal classes of graphs of unbounded clique-width defined by finitely many forbidden induced subgraphs
• Linear clique-width for hereditary classes of cographs
• From Tree-Width to Clique-Width: Excluding a Unit Interval Graph
• scientific article; zbMATH DE number 1439435 (Why is no real title available?)
• A Framework for Minimal Hereditary Classes of Graphs of Unbounded Clique-Width
• \(t\)-sails and sparse hereditary classes of unbounded tree-width
• MSO undecidability for hereditary classes of unbounded clique-width
• An overview of universal obstructions for graph parameters

This page was built for publication: Infinitely many minimal 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 Q2413975)