### Abstract

Hadwiger's conjecture asserts that if a simple graph G has no Kt+1 minor, then its vertex set V (G) can be partitioned into t stable sets. This is still open, but we prove under the same hypothesis that V (G) can be partitioned into t sets X_{1},⋯, X_{t}, such that for 1 ≤ i ≤ t, the subgraph induced on Xi has maximum degree at most a function of t. This is sharp, in that the conclusion becomes false if we ask for a partition into t - 1 sets with the same property.

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

Pages (from-to) | 2385-2388 |

Number of pages | 4 |

Journal | SIAM Journal on Discrete Mathematics |

Volume | 29 |

Issue number | 4 |

DOIs | |

State | Published - Jan 1 2015 |

### All Science Journal Classification (ASJC) codes

- Mathematics(all)

### Keywords

- Hadwiger's conjecture
- Improper coloring
- Minor

## Fingerprint Dive into the research topics of 'A relative of Hadwiger's conjecture'. Together they form a unique fingerprint.

## Cite this

Edwards, K., Kang, D. Y., Kim, J., Oum, S. I., & Seymour, P. (2015). A relative of Hadwiger's conjecture.

*SIAM Journal on Discrete Mathematics*,*29*(4), 2385-2388. https://doi.org/10.1137/141002177