Rainbow structures in locally bounded colorings of graphs

Cited 3 time in webofscience Cited 0 time in scopus
  • Hit : 23
  • Download : 0
We study approximate decompositions of edge-colored quasirandom graphs into rainbow spanning structures: an edge-coloring of a graph is locallyl-bounded if every vertex is incident to at most l edges of each color, and is (globally) g-boundedif every color appears at most g times. Our results imply the existence of: (1) approximate decompositions of properly edge-colored Kn into rainbow almost-spanning cycles; (2) approximate decompositions of edge-colored Kn into rainbow Hamilton cycles, provided that the coloring is (1-o(1))n2-bounded and locally o(nlog4n)-bounded; and (3) an approximate decomposition into full transversals of any nxn array, provided each symbol appears (1-o(1))n times in total and only o(nlog2n) times in each row or column. Apart from the logarithmic factors, these bounds are essentially best possible. We also prove analogues for rainbow F-factors, where F is any fixed graph. Both (1) and (2) imply approximate versions of the Brualdi-Hollingsworth conjecture on decompositions into rainbow spanning trees.
Publisher
WILEY
Issue Date
2020-07
Language
English
Article Type
Article
Citation

RANDOM STRUCTURES & ALGORITHMS, v.56, no.4, pp.1171 - 1204

ISSN
1042-9832
DOI
10.1002/rsa.20902
URI
http://hdl.handle.net/10203/279377
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 3 items in WoS Click to see citing articles in records_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0