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

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 199
  • Download : 0
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.
Publisher
Elsevier
Issue Date
2015-11
Language
English
Article Type
Article
Citation

Electronic Notes in Discrete Mathematics, v.49, pp.133 - 138

ISSN
1571-0653
DOI
10.1016/j.endm.2015.06.020
URI
http://hdl.handle.net/10203/238856
Appears in Collection
MA-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0