A relative of Hadwiger's conjecture

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,\dots ,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.

6 pages

Cited by in corpus (14)

• Improper Colourings inspired by Hadwiger's Conjecture
• Defective colouring of graphs excluding a subgraph or minor
• Clustered 3-Colouring Graphs of Bounded Degree
• Islands in minor-closed classes. I. Bounded treewidth and separators
• Partitioning $H$-minor free graphs into three subgraphs with no large components
• Defective and Clustered Choosability of Sparse Graphs
• Clustered Colouring in Minor-Closed Classes
• Clustered Variants of Hajós' Conjecture
• Clustered Coloring of Graphs Excluding a Subgraph and a Minor
• Improper coloring of graphs with no odd clique minor
• Immersion and clustered coloring
• Colouring Strong Products
• Defective coloring is perfect for minors
• Colourings with Bounded Monochromatic Components in Graphs of Given Circumference