Clique-Width of Graph Classes Defined by Two Forbidden Induced Subgraphs
From MaRDI portal
Publication:2947018
DOI10.1007/978-3-319-18173-8_12zbMath1462.05310arXiv1405.7092OpenAlexW2116334057MaRDI QIDQ2947018
Konrad K. Dabrowski, Daniël Paulusma
Publication date: 21 September 2015
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1405.7092
Structural characterization of families of graphs (05C75) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)
Related Items (9)
Bounding the Clique-Width of H-free Chordal Graphs ⋮ Graph classes with and without powers of bounded clique-width ⋮ Classifying the clique-width of \(H\)-free bipartite graphs ⋮ Induced minor free graphs: isomorphism and clique-width ⋮ A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs ⋮ Bounding the clique-width of \(H\)-free split graphs ⋮ Bounding Clique-Width via Perfect Graphs ⋮ Bounding the clique-width of \(H\)-free split graphs ⋮ Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Colouring of graphs with Ramsey-type forbidden subgraphs
- Determining the chromatic number of triangle-free \(2P_3\)-free graphs in polynomial time
- The coloring problem for classes with two small obstructions
- Some new hereditary classes where graph coloring remains NP-hard
- Updating the complexity status of coloring graphs without a fixed induced linear forest
- Colouring vertices of triangle-free graphs without forests
- 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
- Paw-free graphs
- On variations of \(P_{4}\)-sparse graphs
- 3-colorability and forbidden subgraphs. I: Characterizing pairs
- 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
- Polynomial-time algorithms for minimum weighted colorings of \((P_5, \overline{P}_5)\)-free graphs and similar graph classes
- Clique-width for 4-vertex forbidden subgraphs
- Line graphs of bounded clique-width
- Approximating clique-width and branch-width
- List coloring in the absence of two subgraphs
- Bounding Clique-Width via Perfect Graphs
- Classifying the Clique-Width of H-Free Bipartite Graphs
- Bounding the Clique-Width of H-free Chordal Graphs
- Towards an Isomorphism Dichotomy for Hereditary Graph Classes
- A Survey on the Computational Complexity of Coloring Graphs with Forbidden 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
- 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
- Narrowing the Complexity Gap for Colouring (C s ,P t )-Free Graphs
- GEM- AND CO-GEM-FREE GRAPHS HAVE BOUNDED CLIQUE-WIDTH
- Two cases of polynomial-time solvability for the coloring problem
This page was built for publication: Clique-Width of Graph Classes Defined by Two Forbidden Induced Subgraphs
