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 X1,⋯, Xt, 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 - 2015 |
All Science Journal Classification (ASJC) codes
- General Mathematics
Keywords
- Hadwiger's conjecture
- Improper coloring
- Minor