Back to Search
Start Over
Square roots of minor closed graph classes.
Square roots of minor closed graph classes.
- Source :
-
Discrete Applied Mathematics . May2014, Vol. 168, p34-39. 6p. - Publication Year :
- 2014
-
Abstract
- Abstract: Let be a graph class. The square root of contains all graphs whose squares belong in . We prove that if is non-trivial and minor closed, then all graphs in its square root have carving-width bounded by some constant depending only on . As a consequence, every square root of such a graph class has a linear time recognition algorithm. [Copyright &y& Elsevier]
Details
- Language :
- English
- ISSN :
- 0166218X
- Volume :
- 168
- Database :
- Academic Search Index
- Journal :
- Discrete Applied Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 94692692
- Full Text :
- https://doi.org/10.1016/j.dam.2013.05.026