Rainbow structures in locally bounded colorings of graphs. Issue 4 (13th January 2020)

• Record Type: Journal Article
• Authors: Kim, Jaehoon; Kühn, Daniela; Kupavskii, Andrey; Osthus, Deryk
• Is Part Of: Random structures & algorithms. Volume 56:Issue 4(2020)
• Page Start: 1171
• Page End: 1204
• Publication Date: 2020-01-13
• Subjects: Hamilton cycles -- spanning trees -- rainbow colorings -- Latin squares; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20902
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract : We study approximate decompositions of edge‐colored quasirandom graphs into rainbow spanning structures: an edge‐coloring of a graph is locally ℓ ‐bounded if every vertex is incident to at most ℓ edges of each color, and is (globally) g ‐bounded if every color appears at most g times. Our results imply the existence of: (1) approximate decompositions of properly edge‐colored K n into rainbow almost‐spanning cycles; (2) approximate decompositions of edge‐colored K n into rainbow Hamilton cycles, provided that the coloring is ( 1 − o ( 1 ) ) n 2 ‐bounded and locally o ( n log 4 n ) ‐bounded; and (3) an approximate decomposition into full transversals of any n × n array, provided each symbol appears ( 1 − o ( 1 ) ) n times in total and only o ( n log 2 n ) 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.