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 KnK_n be the complete graph on nn vertices.

Constant-error rainbow tree conjecture. There is a constant CC such that every properly coloured KnK_n has a rainbow copy of every tree on nCn-C vertices.

The paper proves rainbow copies for every tree on no(n)n-o(n) 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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.