Abstract
Let G be a graph class. The square root of G contains all graphs whose square belong in G. We prove that if G is non-trivial and minor closed, then all graphs in its square root have carving-width bounded by some constant depending only on G. As a consequence, every square root of such a graph class has a linear time recognition algorithm.
Original language | English (US) |
---|---|
Pages (from-to) | 681-686 |
Number of pages | 6 |
Journal | Electronic Notes in Discrete Mathematics |
Volume | 38 |
DOIs | |
State | Published - Dec 1 2011 |
Keywords
- Branch-width
- Carving-width
- Graph minors
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics
- Applied Mathematics