Rainbow structures in locally bounded colorings of graphs

Research output: Contribution to journalArticle


Colleges, School and Institutes

External organisations

  • University of Oxford
  • KAIST, Daejeon, S. Korea


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


Original languageEnglish
JournalRandom Structures and Algorithms
Early online date13 Jan 2020
Publication statusE-pub ahead of print - 13 Jan 2020


  • Hamilton cycles, spanning trees, rainbow colorings, Latin squares