A relative of Hadwiger's conjecture
classification
🧮 math.CO
keywords
setsconjecturehadwigerpartitionedsameassertsbecomesconclusion
read the original abstract
Hadwiger's conjecture asserts that if a simple graph $G$ has no $K_{t+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 hypotheses that $V(G)$ can be partitioned into $t$ sets $X_1,\ldots, X_t$, such that for $1\le i\le t$, the subgraph induced on $X_i$ 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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.