Bounding the clique-width of \(H\)-free split graphs

DOI10.1016/j.endm.2015.06.069zbMath1346.05210arXiv1509.04273OpenAlexW2568387990MaRDI QIDQ5890917

Andreas Brandstädt, Shenwei Huang, Daniël Paulusma, Konrad K. Dabrowski

Publication date: 14 October 2016

Published in: Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

perfect graphssplit graphsclique-widthforbidden induced subgraphhereditary graph class

Mathematics Subject Classification ID

Distance in graphs (05C12) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Perfect graphs (05C17) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items

Bounding the Clique-Width of H-free Chordal Graphs, Classifying the clique-width of \(H\)-free bipartite graphs, Bounding the clique-width of \(H\)-free split graphs

Cites Work

• Unnamed Item
• Polynomial-time recognition of clique-width \(\leq 3\) graphs
• Characterising the linear clique-width of a class of graphs by forbidden induced subgraphs
• Recent developments on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• Bounding Clique-Width via Perfect Graphs
• Classifying the Clique-Width of H-Free Bipartite Graphs
• Bounding the Clique-Width of H-free Chordal Graphs
• Clique-Width of Graph Classes Defined by Two Forbidden Induced Subgraphs
• Towards an Isomorphism Dichotomy for Hereditary Graph Classes
• THE CLIQUE-WIDTH OF BIPARTITE GRAPHS IN MONOGENIC CLASSES
• Graph Isomorphism for Graph Classes Characterized by Two Forbidden Induced Subgraphs
• ON THE CLIQUE–WIDTH OF GRAPH WITH FEW P₄'S