Article ID Journal Published Year Pages File Type
6872227 Discrete Applied Mathematics 2014 6 Pages PDF
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.
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,