Rainbow structures in locally bounded colorings of graphs

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‐coloredK ninto rainbow almost‐spanning cycles; (2) approximate decompositions of edge‐coloredK ninto rainbow Hamilton cycles, provided that the coloring is ( 1 − o ( 1 ) ) n 2 ‐bounded and locally o ( nlog 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 ( nlog 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.