Title of article :
Square Roots of Minor Closed Graph Classes
Author/Authors :
Nestoridis، نويسنده , , Nestor V. and Thilikos، نويسنده , , Dimitrios M.، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2011
Pages :
6
From page :
681
To page :
686
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.
Keywords :
Graph Minors , Carving-width , branch-width
Journal title :
Electronic Notes in Discrete Mathematics
Serial Year :
2011
Journal title :
Electronic Notes in Discrete Mathematics
Record number :
1455926
Link To Document :
بازگشت