Logo image
Sign in
Square roots of minor closed graph classes
Journal article   Open access   Peer reviewed

Square roots of minor closed graph classes

Nestor Nestoridis and Dimitrios M. Thilikos
Discrete Applied Mathematics, Vol.168, pp.34 - 39
2014

Abstract

carving-width graph minors branch-width square roots of graphs
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.
url
Find in HALView
url
https://doi.org/10.1016/j.dam.2013.05.026View
Published (Version of record) Open

Metrics

1 Record Views

Details

Logo image