Partitioning H-minor free graphs into three subgraphs with no large components

Chun Hung Liu; Sang il Oum

doi:10.1016/j.endm.2015.06.020

Partitioning H-minor free graphs into three subgraphs with no large components

Chun Hung Liu, Sang il Oum

Mathematics

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

1 Scopus citations

Abstract

We prove that for every graph H, if a graph G has no H minor, then V(G) can be partitioned into three sets such that the subgraph induced on each set has no component of size larger than a function of H and the maximum degree of G. This answers a question of Esperet and Joret and improves a result of Alon, Ding, Oporowski and Vertigan and a result of Esperet and Joret. As a corollary, for every positive integer t, if a graph G has no K_t+1 minor, then V(G) can be partitioned into 3t sets such that the subgraph induced on each set has no component of size larger than a function of t. This corollary improves a result of Wood.

Original language	English (US)
Pages (from-to)	133-138
Number of pages	6
Journal	Electronic Notes in Discrete Mathematics
Volume	49
DOIs	https://doi.org/10.1016/j.endm.2015.06.020
State	Published - Nov 2015

All Science Journal Classification (ASJC) codes

Discrete Mathematics and Combinatorics
Applied Mathematics

Keywords

Coloring
Graph minors
Partitioning

Access to Document

10.1016/j.endm.2015.06.020

Cite this

@article{54a4cc7cb5604bc498ae680186b044cb,

title = "Partitioning H-minor free graphs into three subgraphs with no large components",

abstract = "We prove that for every graph H, if a graph G has no H minor, then V(G) can be partitioned into three sets such that the subgraph induced on each set has no component of size larger than a function of H and the maximum degree of G. This answers a question of Esperet and Joret and improves a result of Alon, Ding, Oporowski and Vertigan and a result of Esperet and Joret. As a corollary, for every positive integer t, if a graph G has no Kt+1 minor, then V(G) can be partitioned into 3t sets such that the subgraph induced on each set has no component of size larger than a function of t. This corollary improves a result of Wood.",

keywords = "Coloring, Graph minors, Partitioning",

author = "Liu, {Chun Hung} and Oum, {Sang il}",

note = "Publisher Copyright: {\textcopyright} 2015 Elsevier B.V.",

year = "2015",

month = nov,

doi = "10.1016/j.endm.2015.06.020",

language = "English (US)",

volume = "49",

pages = "133--138",

journal = "Electronic Notes in Discrete Mathematics",

issn = "1571-0653",

publisher = "Elsevier",

}

TY - JOUR

T1 - Partitioning H-minor free graphs into three subgraphs with no large components

AU - Liu, Chun Hung

AU - Oum, Sang il

PY - 2015/11

Y1 - 2015/11

N2 - We prove that for every graph H, if a graph G has no H minor, then V(G) can be partitioned into three sets such that the subgraph induced on each set has no component of size larger than a function of H and the maximum degree of G. This answers a question of Esperet and Joret and improves a result of Alon, Ding, Oporowski and Vertigan and a result of Esperet and Joret. As a corollary, for every positive integer t, if a graph G has no Kt+1 minor, then V(G) can be partitioned into 3t sets such that the subgraph induced on each set has no component of size larger than a function of t. This corollary improves a result of Wood.

AB - We prove that for every graph H, if a graph G has no H minor, then V(G) can be partitioned into three sets such that the subgraph induced on each set has no component of size larger than a function of H and the maximum degree of G. This answers a question of Esperet and Joret and improves a result of Alon, Ding, Oporowski and Vertigan and a result of Esperet and Joret. As a corollary, for every positive integer t, if a graph G has no Kt+1 minor, then V(G) can be partitioned into 3t sets such that the subgraph induced on each set has no component of size larger than a function of t. This corollary improves a result of Wood.

KW - Coloring

KW - Graph minors

KW - Partitioning

UR - http://www.scopus.com/inward/record.url?scp=84947782392&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84947782392&partnerID=8YFLogxK

U2 - 10.1016/j.endm.2015.06.020

DO - 10.1016/j.endm.2015.06.020

M3 - Article

AN - SCOPUS:84947782392

SN - 1571-0653

VL - 49

SP - 133

EP - 138

JO - Electronic Notes in Discrete Mathematics

JF - Electronic Notes in Discrete Mathematics

ER -

Partitioning H-minor free graphs into three subgraphs with no large components

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this