Constant-error rainbow tree embedding conjecture
Constant-error rainbow tree embedding conjecture
A properly coloured graph is an edge-coloured graph in which edges sharing a vertex have distinct colours. A subgraph is rainbow if all its edges have distinct colours. Let be the complete graph on vertices.
Constant-error rainbow tree conjecture. There is a constant such that every properly coloured has a rainbow copy of every tree on vertices.
The paper proves rainbow copies for every tree on vertices and explains that the error term cannot be zero. The conjecture asks whether the error can be reduced to a constant.
Sources & referencesView supporting material
Primary source
Richard Montgomery, Alexey Pokrovskiy and Benny Sudakov, “Embedding rainbow trees with applications to graph labelling and decomposition”, arXiv:1803.03316 (2018).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.