A relative of Hadwiger's conjecture

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

doi:10.1137/141002177

A relative of Hadwiger's conjecture

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

Mathematics

Research output: Contribution to journal › Article › peer-review

30 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 X₁,⋯, X_t, 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	https://doi.org/10.1137/141002177
State	Published - 2015

All Science Journal Classification (ASJC) codes

General Mathematics

Keywords

Hadwiger's conjecture
Improper coloring
Minor

Access to Document

10.1137/141002177

Cite this

@article{dabc80c59e6d4e53a092c2bbe42f4b6e,

title = "A relative of Hadwiger's conjecture",

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.",

keywords = "Hadwiger's conjecture, Improper coloring, Minor",

author = "Katherine Edwards and Kang, \{Dong Yeap\} and Jaehoon Kim and Oum, \{Sang Il\} and Paul Seymour",

note = "Publisher Copyright: {\textcopyright} 2015 Society for Industrial and Applied Mathematics.",

year = "2015",

doi = "10.1137/141002177",

language = "English (US)",

volume = "29",

pages = "2385--2388",

journal = "SIAM Journal on Discrete Mathematics",

issn = "0895-4801",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "4",

}

TY - JOUR

T1 - A relative of Hadwiger's conjecture

AU - Edwards, Katherine

AU - Kang, Dong Yeap

AU - Kim, Jaehoon

AU - Oum, Sang Il

AU - Seymour, Paul

PY - 2015

Y1 - 2015

N2 - 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.

AB - 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.

KW - Hadwiger's conjecture

KW - Improper coloring

KW - Minor

UR - https://www.scopus.com/pages/publications/84953256245

UR - https://www.scopus.com/pages/publications/84953256245#tab=citedBy

U2 - 10.1137/141002177

DO - 10.1137/141002177

M3 - Article

AN - SCOPUS:84953256245

SN - 0895-4801

VL - 29

SP - 2385

EP - 2388

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

IS - 4

ER -

A relative of Hadwiger's conjecture

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this