The project focuses on the existence of rainbow spanning trees in edge-colored complete graphs. As a starting point, Brualdi and Hollingsworth [2] conjectured the following.
Conjecture (Brualdi and Hollingsworth): For k at least 3 and for any edge-coloring of a complete graph on 2k vertices by perfect matchings, a full partition into rainbow spanning trees is always possible.
A strengthening was proposed by Kaneko et al. [9], stating that for any proper edge-coloring of a complete graph on at least 5 vertices, there exists n/2 rainbow spanning trees. Constantine [4] suggested that the spanning trees in the conjecture can be chosen to be isomorphic to each other. For further results, see [5,7,10,11]. Recently, Glock et al. [6] verified the conjecture as well as its strengthening by Constantine for large enough values of k. The existence of disjoint rainbow spanning trees was also considered for not necessarily proper edge-colorings. Akbari and Alipour [1] showed that each complete graph on n vertices that is edge-colored such that no color appears more than n/2 times contains at least two rainbow spanning trees. Under the same assumption, Carraher et al. [3] verified the existence of O(n/\log n) rainbow spanning trees. General graphs were considered in [8].
One of the simplest open cases that we would like to resolve is when the graph can be partitioned into two spanning trees.
Problem: Let G=(V,E) be a graph that can be partitioned into two spanning trees, and consider a coloring of the edges with n-1 colors so that each color appears exactly twice. Decide if there exists a partitioning into two rainbow spanning trees.
The goal of the project is to make further progress in these questions.
Referenciák
[1] S. Akbari and A. Alipour. Multicolored trees in complete graphs.Journal of Graph Theory, 54(3):221–232, 2007.
[2] R. A. Brualdi and S. Hollingsworth. Multicolored trees in complete graphs. Journal of Combinatorial Theory, Series B, 68(2):310–313, 1996.
[3] J. M. Carraher, S. G. Hartke, and P. Horn. Edge-disjoint rainbow spanning trees in complete graphs. European Journal of Combinatorics, 57:71–84, 2016.
[4] G. M. Constantine. Edge-disjoint isomorphic multicolored trees and cycles in complete graphs. SIAM Journal on Discrete Mathematics, 18(3):577–580, 2004.
[5] H.-L. Fu, Y.-H. Lo, K. E. Perry, and C. A. Rodger. On the number of rainbow spanning trees in edge-colored complete graphs. Discrete Mathematics, 341(8):2343–2352, 2018.
[6] S. Glock, D. Kühn, R. Montgomery, and D. Osthus. Decompositions into isomorphic rainbow spanningtrees. Journal of Combinatorial Theory, Series B, 146:439–484, 2021.
[7] P. Horn. Rainbow spanning trees in complete graphs colored by one-factorizations. Journal of Graph Theory, 87(3):333–346, 2018.
[8] P. Horn and L. M. Nelsen. Many edge-disjoint rainbow spanning trees in general graphs. arXiv preprint arXiv:1704.00048, 2017.
[9] A. Kaneko, M. Kano, and K. Suzuki. Three edge disjoint multicolored spanning trees in completegraphs. Preprint, 2003.
[10] R. Montgomery, A. Pokrovskiy, and B. Sudakov. Decompositions into spanning rainbow structures. Proceedings of the London Mathematical Society, 119(4):899–959, 2019.
[11] A. Pokrovskiy and B. Sudakov. Linearly many rainbow trees in properly edge-coloured complete graphs. Journal of Combinatorial Theory, Series B, 132:134–156, 2018.