Square roots of minor closed graph classes

Nestor V. Nestoridis, Dimitrios M. Thilikos

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)34-39
Number of pages6
JournalDiscrete Applied Mathematics
StatePublished - May 11 2014


  • Branch-width
  • Carving-width
  • Graph minors
  • Square roots of graphs

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics


Dive into the research topics of 'Square roots of minor closed graph classes'. Together they form a unique fingerprint.

Cite this