2018/05/22 by Jaehoon Kim, Kim, Jaehoon, Daniela Kühn +5
Computer Science · Mathematics · #05B15 #05B40 #05C45 #05C70 #05D15 #05D40 #Advanced Graph Theory Research #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1805.08424
openalex publication_date 2018/05/22 · openalex created_date 2020/01/23 · openalex updated_date 2026/07/28
We prove several results on approximate decompositions of edge-coloured quasirandom graphs into rainbow spanning structures. More precisely, we say that an edge-colouring of a graph is locally ℓ-bounded if no vertex is incident to more than ℓ edges of any given colour, and that it is (globally) g-bounded if no colour appears more than g times in the colouring. Note that every proper colouring of an n-vertex graph is locally 1-bounded, and (globally) n/2-bounded. Our results imply the following: (i) The existence of approximate decompositions of edge-coloured Kn into rainbow almost-spanning cycles, provided that the colouring is (n)/(2)-bounded and locally o(n)-bounded. (ii) The existence of approximate decompositions of edge-coloured Kn into rainbow Hamilton cycles, provided that the colouring is (1-o(1))\frac n2-bounded and locally o((n)/(log4 n))-bounded. (iii) A bipartite version of our results implies that every n× n array, where each symbol appears (1-o(1))n times in total and appears only o((n)/(log2 n)) times in each row or column, has an approximate decomposition into full transversals. We also prove analogues of (i) and (ii) for F-factors, where F is any fixed graph. Apart from the logarithmic factor in (ii), all these bounds are essentially best possible. (i) can be viewed as a generalization of a recent result of Alon, Pokrovskiy and Sudakov, who showed the existence of an almost spanning cycle in a properly coloured complete graph. Both (i) and (ii) imply approximate versions of a conjecture of Brualdi and Hollingsworth, stating that every properly edge-coloured complete graph can be decomposed into rainbow spanning trees.