Clique-width and edge contraction
From MaRDI portal
Abstract: We prove that edge contractions do not preserve the property that a set of graphs has bounded clique-width. This property is preserved by contractions of edges, one end of which is a vertex of degree 2.
Cites work
- Approximating clique-width and branch-width
- Graph structure and monadic second-order logic. A language-theoretic approach
- Graphs of linear clique-width at most 3
- scientific article; zbMATH DE number 1161563 (Why is no real title available?)
- Linear time solvable optimization problems on graphs of bounded clique-width
- Monadic second-order definable graph transductions: a survey
- Multicut on graphs of bounded clique-width
- On the clique-width of some perfect graph classes
- Parametrized complexity theory.
- Polynomial-time recognition of clique-width 3 graphs
- Rank-width and vertex-minors
- Recent developments on graphs of bounded clique-width
- The rank-width of the square grid
- Upper bounds to the clique width of graphs
Cited in
(13)- Grammars and clique-width bounds from split decompositions
- A characterisation of clique-width through nested partitions
- Rank-width: algorithmic and structural results
- Bounding clique-width via perfect graphs
- Bounding clique-width via perfect graphs
- Well-quasi-ordering versus clique-width: new results on bigenic classes
- Tree pivot-minors and linear rank-width
- The behavior of clique-width under graph operations and graph transformations
- Clique-width and well-quasi-ordering of triangle-free graph classes
- Clique-width of point configurations
- Tree pivot-minors and linear rank-width
- On using SAT solvers for graph computations
- Well-quasi-ordering versus clique-width: new results on bigenic classes
This page was built for publication: Clique-width and edge contraction
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2350597)
