pith. sign in

arxiv: 1407.5236 · v3 · pith:SDAZ4NMVnew · submitted 2014-07-20 · 🧮 math.CO

A relative of Hadwiger's conjecture

classification 🧮 math.CO
keywords setsconjecturehadwigerpartitionedsameassertsbecomesconclusion
0
0 comments X
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.