Square Roots of Minor Closed Graph Classes

Nestor V. Nestoridis, Dimitrios M. Thilikos

Research output: Contribution to journalArticlepeer-review

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.

Original languageEnglish (US)
Pages (from-to)681-686
Number of pages6
JournalElectronic Notes in Discrete Mathematics
Volume38
DOIs
StatePublished - Dec 1 2011

Keywords

  • Branch-width
  • Carving-width
  • Graph minors

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Square Roots of Minor Closed Graph Classes'. Together they form a unique fingerprint.

Cite this