Clique-width for hereditary graph classes
From MaRDI portal
Abstract: Clique-width is a well-studied graph parameter owing to its use in understanding algorithmic tractability: if the clique-width of a graph class is bounded by a constant, a wide range of problems that are NP-complete in general can be shown to be polynomial-time solvable on . For this reason, the boundedness or unboundedness of clique-width has been investigated and determined for many graph classes. We survey these results for hereditary graph classes, which are the graph classes closed under taking induced subgraphs. We then discuss the algorithmic consequences of these results, in particular for the Colouring and Graph Isomorphism problems. We also explain a possible strong connection between results on boundedness of clique-width and on well-quasi-orderability by the induced subgraph relation for hereditary graph classes.
Recommendations
Cited in
(36)- Clique-width and the speed of hereditary properties
- Critical properties of graphs of bounded clique-width
- The Weisfeiler-Leman dimension of chordal bipartite graphs without bipartite claw
- Uncountably many minimal hereditary classes of graphs of unbounded clique-width
- Partitioning \(H\)-free graphs of bounded diameter
- List k-colouring P_t-free graphs: a mim-width perspective
- Polynomially bounding the number of minimal separators in graphs: reductions, sufficient conditions, and a dichotomy theorem
- Minimal classes of graphs of unbounded clique-width defined by finitely many forbidden induced subgraphs
- Graph isomorphism for \((H_1, H_2)\)-free graphs: an almost complete dichotomy
- Steiner trees for hereditary graph classes: a treewidth perspective
- On algorithmic applications of sim-width and mim-width of (H₁,H₂)-free graphs
- Linear clique-width for hereditary classes of cographs
- Clique cycle-transversals in distance-hereditary graphs
- scientific article; zbMATH DE number 1979486 (Why is no real title available?)
- Treewidth versus clique number. I: Graph classes with a forbidden structure
- Tree pivot-minors and linear rank-width
- scientific article; zbMATH DE number 7204407 (Why is no real title available?)
- Clique-width for graph classes closed under complementation
- Graphs of bounded cliquewidth are polynomially -bounded
- Hereditary graph classes: When the complexities of <scp>coloring</scp> and <scp>clique cover</scp> coincide
- Faster 3-coloring of small-diameter graphs
- Finding matching cuts in \(H\)-free graphs
- Bounding the mim‐width of hereditary graph classes
- Clique‐width: Harnessing the power of atoms
- Contracting to a longest path in H-free graphs
- A class of graphs with large rankwidth
- (Theta, triangle)‐free and (even hole, K4)‐free graphs. Part 2: Bounds on treewidth
- Bounding the Mim-Width of Hereditary Graph Classes.
- Treewidth versus clique number. II: Tree-independence number
- Solving problems on generalized convex graphs via mim-width
- Dichotomies for maximum matching cut: \(H\)-freeness, bounded diameter, bounded radius
- Comparing width parameters on graph classes
- Extension preservation on dense graph classes
- Bounding width on graph classes of constant diameter
- Solving problems on generalized convex graphs via mim-width
- Recent developments on graphs of bounded clique-width
This page was built for publication: Clique-width for hereditary graph classes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5149166)
