Infinitely many minimal classes of graphs of unbounded clique-width

DOI10.1016/j.dam.2017.02.012zbMath1395.05051arXiv1701.08857OpenAlexW2585972132MaRDI QIDQ2413975

Nicholas Korpelainen, Jan Foniok, Vadim V. Lozin, Andrew J. Collins, 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

zbMATH Keywords

clique-widthhereditary classlinear clique-width

Mathematics Subject Classification ID

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

Related Items (5)

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 ⋮ Between clique-width and linear clique-width of bipartite graphs ⋮ A Framework for Minimal Hereditary Classes of Graphs of Unbounded Clique-Width ⋮ The grid theorem for vertex-minors

Cites Work

• Unnamed Item
• Well-quasi-order of relabel functions
• Minimal classes of graphs of unbounded clique-width
• Graph minors. XX: Wagner's conjecture
• On canonical antichains
• Graph minors. V. Excluding a planar graph
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• Handle-rewriting hypergraph grammars
• Approximating clique-width and branch-width
• Rank-width and vertex-minors
• Well-quasi-ordering Does Not Imply Bounded Clique-width
• Linear Clique‐Width for Hereditary Classes of Cographs

This page was built for publication: Infinitely many minimal classes of graphs of unbounded clique-width