Bounding clique-width via perfect graphs
From MaRDI portal
Publication:2424685
DOI10.1016/j.jcss.2016.06.007zbMath1428.05220arXiv1406.6298OpenAlexW2623827933MaRDI QIDQ2424685
Konrad K. Dabrowski, Shenwei Huang, Daniël Paulusma
Publication date: 25 June 2019
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1406.6298
Distance in graphs (05C12) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)
Related Items (8)
Colouring diamond-free graphs ⋮ Graph isomorphism for \((H_1, H_2)\)-free graphs: an almost complete dichotomy ⋮ Bounding the mim‐width of hereditary graph classes ⋮ Clique‐width: Harnessing the power of atoms ⋮ Special issue: Selected papers of the 9th international conference on language and automata theory and applications, LATA 2015 ⋮ Clique-Width for Graph Classes Closed under Complementation ⋮ Bounding the Mim-Width of Hereditary Graph Classes. ⋮ Clique-width and well-quasi-ordering of triangle-free graph classes
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Colouring of graphs with Ramsey-type forbidden subgraphs
- Polynomial-time recognition of clique-width \(\leq 3\) graphs
- 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
- Classifying the clique-width of \(H\)-free bipartite graphs
- 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
- Approximating clique-width and branch-width
- Normal hypergraphs and the perfect graph conjecture
- Bounding Clique-Width via Perfect Graphs
- Bounding the Clique-Width of H-free Chordal Graphs
- A SAT Approach to Clique-Width
- Towards an Isomorphism Dichotomy for Hereditary Graph Classes
- 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
- Graph Isomorphism for Graph Classes Characterized by Two Forbidden Induced Subgraphs
- ON THE CLIQUE–WIDTH OF GRAPH WITH FEW P4'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
- Bounding the clique-width of \(H\)-free split graphs
This page was built for publication: Bounding clique-width via perfect graphs