Bounding the clique-width of H-free split graphs

DOI10.1016/J.DAM.2016.04.003MaRDI QIDQ5965534zbMATH OpenOpenAlexFDO

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

Publication date 2 November 2016

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

Full work available at URL https://doi.org/10.1016/j.dam.2016.04.003

zbMATH Keywords

split graphclique-widthperfect graphforbidden induced subgraphhereditary graph class

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) Perfect graphs (05C17)

Recommendations

• Bounding the clique-width of \(H\)-free split graphs
• Bounding the clique-width of \(H\)-free chordal graphs
• Bounding the Clique‐Width of H‐Free Chordal Graphs
• Bounding clique-width via perfect graphs
• Classifying the clique-width of \(H\)-free bipartite graphs

Cites work

• scientific article; zbMATH DE number 3632548 (Why is no real title available?)
• scientific article; zbMATH DE number 1979486 (Why is no real title available?)
• scientific article; zbMATH DE number 5279372 (Why is no real title available?)
• Bounding clique-width via perfect graphs
• Bounding the clique-width of \(H\)-free chordal graphs
• Bounding the clique-width of \(H\)-free split graphs
• Characterising the linear clique-width of a class of graphs by forbidden induced subgraphs
• Chordal co-gem-free and (\(P_{5}\),\,gem)-free graphs have bounded clique-width
• Classifying the clique-width of \(H\)-free bipartite graphs
• Clique-width for 4-vertex forbidden subgraphs
• Clique-width of graph classes defined by two forbidden induced subgraphs
• Colouring of graphs with Ramsey-type forbidden subgraphs
• Colouring vertices of triangle-free graphs without forests
• GEM- AND CO-GEM-FREE GRAPHS HAVE BOUNDED CLIQUE-WIDTH
• Graph classes with and without powers of bounded clique-width
• Graph isomorphism for graph classes characterized by two forbidden induced subgraphs
• Maximum Weight Stable Set on graphs without claw and co-claw (and similar graph classes) can be solved in linear time.
• On the Band-, Tree-, and Clique-Width of Graphs with Bounded Vertex Degree
• On the clique-width of graph with few \(P_{4}\)'s
• On the clique-width of some perfect graph classes
• On the structure of (\(P_{5}\),\,gem)-free graphs
• On variations of \(P_{4}\)-sparse graphs
• Polynomial-time recognition of clique-width \(\leq 3\) graphs
• Recent developments on graphs of bounded clique-width
• THE CLIQUE-WIDTH OF BIPARTITE GRAPHS IN MONOGENIC CLASSES
• The strong perfect graph theorem
• The tree- and clique-width of bipartite graphs in special classes
• Towards an Isomorphism Dichotomy for Hereditary Graph Classes
• Upper bounds to the clique width of graphs

Cited in

(15)

• Optimal centrality computations within bounded clique-width graphs
• Between clique-width and linear clique-width of bipartite graphs
• Bounding the clique-width of \(H\)-free split graphs
• Clique‐width: Harnessing the power of atoms
• Bounding the Clique‐Width of H‐Free Chordal Graphs
• Classifying the clique-width of \(H\)-free bipartite graphs
• Classifying the clique-width of \(H\)-free bipartite graphs
• Bounding the clique-width of \(H\)-free chordal graphs
• Colouring diamond-free graphs
• Bounding clique-width via perfect graphs
• Clique-width for graph classes closed under complementation
• A class of graphs with large rankwidth
• Graph isomorphism for \((H_1, H_2)\)-free graphs: an almost complete dichotomy
• scientific article; zbMATH DE number 7204407 (Why is no real title available?)
• On the number of maximal independent sets in minimum colorings of split graphs

This page was built for publication: Bounding the clique-width of \(H\)-free split graphs

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