A new graph construction of unbounded clique-width

DOI10.1016/J.ENDM.2016.11.005MaRDI QIDQ509276zbMATH OpenOpenAlexFDO

Authors Nicholas Korpelainen

Publication date 9 February 2017

Full work available at URL https://doi.org/10.1016/j.endm.2016.11.005

zbMATH Keywords

clique-widthhereditary graph classes

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Distance in graphs (05C12) Structural characterization of families of graphs (05C75)

Recommendations

• scientific article; zbMATH DE number 2191997
• Minimal classes of graphs of unbounded clique-width defined by finitely many forbidden induced subgraphs
• Clique-width of graph classes defined by two forbidden induced subgraphs
• Uncountably many minimal hereditary classes of graphs of unbounded clique-width
• Between clique-width and linear clique-width of bipartite graphs

Cites work

• scientific article; zbMATH DE number 1979486 (Why is no real title available?)
• scientific article; zbMATH DE number 2191997 (Why is no real title available?)
• Bipartite graphs of large clique-width
• Graph minors. V. Excluding a planar graph
• Handle-rewriting hypergraph grammars
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• Linear time solvable optimization problems on graphs of bounded clique-width
• Minimal classes of graphs of unbounded clique-width
• On easy and hard hereditary classes of graphs with respect to the independent set problem
• THE CLIQUE-WIDTH OF BIPARTITE GRAPHS IN MONOGENIC CLASSES
• The tree- and clique-width of bipartite graphs in special classes
• Upper bounds to the clique width of graphs

Cited in

(8)

• Uncountably many minimal hereditary classes of graphs of unbounded clique-width
• scientific article; zbMATH DE number 1439435 (Why is no real title available?)
• scientific article; zbMATH DE number 2191997 (Why is no real title available?)
• Critical properties of bipartite permutation graphs
• MSO undecidability for hereditary classes of unbounded clique-width
• Bipartite graphs of large clique-width
• A Framework for Minimal Hereditary Classes of Graphs of Unbounded Clique-Width
• Minimal classes of graphs of unbounded clique-width defined by finitely many forbidden induced subgraphs

This page was built for publication: A new graph construction of unbounded clique-width

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