Rainbow structures in locally bounded colorings of graphs

Jaehoon Kim, Daniela Kuhn, Andrey Kupavskii, Deryk Osthus

Research output: Contribution to journalArticlepeer-review

7 Citations (Scopus)
171 Downloads (Pure)

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 𝐾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
Pages (from-to)1171-1204
JournalRandom Structures and Algorithms
Volume56
Issue number4
Early online date13 Jan 2020
DOIs
Publication statusE-pub ahead of print - 13 Jan 2020

Keywords

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

Fingerprint

Dive into the research topics of 'Rainbow structures in locally bounded colorings of graphs'. Together they form a unique fingerprint.

Cite this