-
Tony Huynh, Aharoni’s rainbow cycle conjecture holds up to an additive constant
Tony Huynh, Aharoni’s rainbow cycle conjecture holds up to an additive constant
In 2017, Aharoni proposed the following generalization of the Caccetta-Häggkvist conjecture for digraphs. If G is a simple n-vertex edge-colored graph with n color classes of size at least r, then G contains a rainbow cycle of length at most ⌈n/r⌉. In this talk, we prove that Aharoni's conjecture holds up to an additive constant. …