Partitioning H-minor free graphs into three subgraphs with no large components Academic Article uri icon

abstract

  • 2017 Elsevier Inc. We prove that for every graph H, if a graph G has no (odd) H minor, then its vertex set V(G) can be partitioned into three sets X 1 , X 2 , X 3 such that for each i, the subgraph induced on X i has no component of size larger than a function of H and the maximum degree of G. This improves a previous result of Alon, Ding, Oporowski and Vertigan (2003) [1] stating that V(G) can be partitioned into four such sets if G has no H minor. Our theorem generalizes a result of Esperet and Joret (2014) [9], who proved it for graphs embeddable on a fixed surface and asked whether it is true for graphs with no H minor. As a corollary, we prove that for every positive integer t, if a graph G has no K t+1 minor, then its vertex set V(G) can be partitioned into 3t sets X 1 ,,X 3t such that for each i, the subgraph induced on X i has no component of size larger than a function of t. This corollary improves a result of Wood (2010) [21], which states that V(G) can be partitioned into 3.5t+2 such sets.

published proceedings

  • Journal of Combinatorial Theory Series B

altmetric score

  • 0.75

author list (cited authors)

  • Liu, C., & Oum, S.

citation count

  • 9

complete list of authors

  • Liu, Chun-Hung||Oum, Sang-il

publication date

  • January 2018