Bounding Clique-Width via Perfect Graphs

DOI10.1007/978-3-319-15579-1_53zbMath1425.05117OpenAlexW2963554170MaRDI QIDQ2799217

Konrad K. Dabrowski, Daniël Paulusma, Shenwei Huang

Publication date: 8 April 2016

Published in: Language and Automata Theory and Applications (Search for Journal in Brave)

Full work available at URL: http://dro.dur.ac.uk/14239/1/14239.pdf

zbMATH Keywords

forbidden induced subgraphsclique-widthgraph class

Mathematics Subject Classification ID

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 (11)

Bounding the Clique-Width of H-free Chordal Graphs ⋮ Clique-Width of Graph Classes Defined by Two Forbidden Induced Subgraphs ⋮ Graph classes with and without powers of bounded clique-width ⋮ Bounding clique-width via perfect graphs ⋮ Classifying the clique-width of \(H\)-free bipartite graphs ⋮ A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs ⋮ Bounding the clique-width of \(H\)-free split graphs ⋮ Well-quasi-ordering versus clique-width: new results on bigenic classes ⋮ Bounding the clique-width of \(H\)-free split graphs ⋮ Unnamed Item ⋮ Well-Quasi-Ordering versus Clique-Width: New Results on Bigenic Classes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Colouring of graphs with Ramsey-type forbidden subgraphs
• Colouring vertices of triangle-free graphs without forests
• The strong perfect graph theorem
• MSOL partitioning problems on graphs of bounded treewidth and clique-width
• Graph classes with and without powers of bounded clique-width
• Recent developments on graphs of bounded clique-width
• On variations of \(P_{4}\)-sparse graphs
• On the structure of (\(P_{5}\),\,gem)-free graphs
• Chordal co-gem-free and (\(P_{5}\),\,gem)-free graphs have bounded clique-width
• Maximum Weight Stable Set on graphs without claw and co-claw (and similar graph classes) can be solved in linear time.
• Edge dominating set and colorings on graphs with fixed clique-width
• Linear time solvable optimization problems on graphs of bounded clique-width
• Clique-width and edge contraction
• Clique-width for 4-vertex forbidden subgraphs
• Line graphs of bounded clique-width
• Approximating clique-width and branch-width
• Classifying the Clique-Width of H-Free Bipartite Graphs
• Clique-Width of Graph Classes Defined by Two Forbidden Induced Subgraphs
• THE CLIQUE-WIDTH OF BIPARTITE GRAPHS IN MONOGENIC CLASSES
• Clique-Width is NP-Complete
• On the Band-, Tree-, and Clique-Width of Graphs with Bounded Vertex Degree
• Approximating rank-width and clique-width quickly
• ON THE CLIQUE–WIDTH OF GRAPH WITH FEW P₄'S
• ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
• On the Relationship Between Clique-Width and Treewidth
• GEM- AND CO-GEM-FREE GRAPHS HAVE BOUNDED CLIQUE-WIDTH

This page was built for publication: Bounding Clique-Width via Perfect Graphs