Colour-separated decomposition of rainbow expanders

Question 10.2 · arXiv:2309.04460

arXiv Question high confidence— first stated 2025-02-26

Authors: Noga Alon, Matija Bucić, Lisa Sauermann, Dmitrii Zakharov, Or Zamir

Question. Does there exist a constant $C>0$ such that the edges of any $n$-vertex properly edge-coloured robust sublinear expander $G$ with average degree at least $C\log n$ can be decomposed into two spanning connected subgraphs in such a way that every colour appears on only one of them?

Context

Appears in Section 10 of the paper, which collects open questions remaining after the main results on rainbow cycles and the connections to additive number theory for non-abelian groups.

Source paper

Essentially tight bounds for rainbow cycles in proper edge-colourings
Noga Alon, Matija Bucić, Lisa Sauermann, Dmitrii Zakharov, Or Zamir · 2025-02-26
https://arxiv.org/abs/2309.04460