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

Cited 12 time in webofscience Cited 0 time in scopus
  • Hit : 628
  • 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
ACADEMIC PRESS INC ELSEVIER SCIENCE
Issue Date
2018-01
Language
English
Article Type
Article
Keywords

HADWIGERS CONJECTURE; TREE-DECOMPOSITION; WIDTH

Citation

JOURNAL OF COMBINATORIAL THEORY SERIES B, v.128, pp.114 - 133

ISSN
0095-8956
DOI
10.1016/j.jctb.2017.08.003
URI
http://hdl.handle.net/10203/211874
Appears in Collection
MA-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡ Click to see webofscience_button
⊙ Cited 12 items in WoS Click to see citing articles in records_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0