Clique-width of graph classes defined by two forbidden induced subgraphs
From MaRDI portal
Abstract: If a graph has no induced subgraph isomorphic to any graph in a finite family , it is said to be -free. The class of -free graphs has bounded clique-width if and only if is an induced subgraph of the 4-vertex path . We study the (un)boundedness of the clique-width of graph classes defined by two forbidden induced subgraphs and . Prior to our study it was not known whether the number of open cases was finite. We provide a positive answer to this question. To reduce the number of open cases we determine new graph classes of bounded clique-width and new graph classes of unbounded clique-width. For obtaining the latter results we first present a new, generic construction for graph classes of unbounded clique-width. Our results settle the boundedness or unboundedness of the clique-width of the class of -free graphs (i) for all pairs , both of which are connected, except two non-equivalent cases, and (ii) for all pairs , at least one of which is not connected, except 11 non-equivalent cases. We also consider classes characterized by forbidding a finite family of graphs as subgraphs, minors and topological minors, respectively, and completely determine which of these classes have bounded clique-width. Finally, we show algorithmic consequences of our results for the graph colour
Recommendations
Cites work
- 3-colorability and forbidden subgraphs. I: Characterizing pairs
- A survey on the computational complexity of coloring graphs with forbidden subgraphs
- Approximating clique-width and branch-width
- Approximating rank-width and clique-width quickly
- Bounding clique-width via perfect graphs
- Bounding the clique-width of H-free chordal graphs
- 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 is NP-complete
- Colouring of graphs with Ramsey-type forbidden subgraphs
- Colouring vertices of triangle-free graphs without forests
- Determining the chromatic number of triangle-free 2P₃-free graphs in polynomial time
- Edge dominating set and colorings on graphs with fixed clique-width
- 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
- scientific article; zbMATH DE number 1979486 (Why is no real title available?)
- scientific article; zbMATH DE number 2044928 (Why is no real title available?)
- scientific article; zbMATH DE number 2044943 (Why is no real title available?)
- scientific article; zbMATH DE number 1833071 (Why is no real title available?)
- scientific article; zbMATH DE number 5279372 (Why is no real title available?)
- Line graphs of bounded clique-width
- Linear time solvable optimization problems on graphs of bounded clique-width
- List coloring in the absence of two subgraphs
- Maximum Weight Stable Set on graphs without claw and co-claw (and similar graph classes) can be solved in linear time.
- MSOL partitioning problems on graphs of bounded treewidth and clique-width
- Narrowing the complexity gap for colouring \((C_{s},P_{t})\)-free graphs
- 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
- Paw-free graphs
- Polynomial-time algorithms for minimum weighted colorings of \((P_5, \overline{P}_5)\)-free graphs and similar graph classes
- Recent developments on graphs of bounded clique-width
- Some new hereditary classes where graph coloring remains NP-hard
- THE CLIQUE-WIDTH OF BIPARTITE GRAPHS IN MONOGENIC CLASSES
- The coloring problem for classes with two small obstructions
- The tree- and clique-width of bipartite graphs in special classes
- Towards an Isomorphism Dichotomy for Hereditary Graph Classes
- Two cases of polynomial-time solvability for the coloring problem
- Updating the complexity status of coloring graphs without a fixed induced linear forest
Cited in
(16)- Treewidth versus clique number in graph classes with a forbidden structure
- Bounding clique-width via perfect graphs
- Minimal classes of graphs of unbounded clique-width defined by finitely many forbidden induced 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
- A survey on the computational complexity of coloring graphs with forbidden subgraphs
- Treewidth versus clique number. I: Graph classes with a forbidden structure
- A new graph construction of unbounded clique-width
- scientific article; zbMATH DE number 7204407 (Why is no real title available?)
- Clique-width for graph classes closed under complementation
- Bounding the clique-width of \(H\)-free split graphs
- Bounding the clique-width of \(H\)-free split graphs
- Clique‐width: Harnessing the power of atoms
- Graph classes with and without powers of bounded clique-width
- Classifying the clique-width of \(H\)-free bipartite graphs
This page was built for publication: Clique-width of graph classes defined by two forbidden induced subgraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2947018)
