A relative of Hadwiger's conjecture

Katherine Edwards, Dong Yeap Kang, Jaehoon Kim, Sang Il Oum, Paul Seymour

Research output: Contribution to journalArticlepeer-review

24 Scopus citations

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 languageEnglish (US)
Pages (from-to)2385-2388
Number of pages4
JournalSIAM Journal on Discrete Mathematics
Volume29
Issue number4
DOIs
StatePublished - 2015

All Science Journal Classification (ASJC) codes

  • General Mathematics

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