## Abstract

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.

Original language | English (US) |
---|---|

Pages (from-to) | 114-133 |

Number of pages | 20 |

Journal | Journal of Combinatorial Theory. Series B |

Volume | 128 |

DOIs | |

State | Published - Jan 2018 |

## All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics

## Keywords

- Graph minors
- Odd minors
- Small components
- Vertex partitions