Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6872227 | Discrete Applied Mathematics | 2014 | 6 Pages |
Abstract
Let G be a graph class. The square root of G contains all graphs whose squares 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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Nestor V. Nestoridis, Dimitrios M. Thilikos,