On Aharoni's rainbow generalization of the Caccetta-Haggkvist conjecture

Abstrakt

For a digraph G and v is an element of V(G), let delta(+)(v) be the number of out-neighbors of v in G. The Caccetta-Haggkvist conjecture states that for all k >= 1, if G is a digraph with n = |V(G)| such that delta(+)(v) >= k for all v is an element of V(G), then G contains a directed cycle of length at most [n/k].

In Aharoni et al. (2019), Aharoni proposes a generalization of this conjecture, that a simple edge-colored graph on n vertices with n color classes, each of size k, has a rainbow cycle of length at most.n/k.. In this paper, we prove this conjecture if each color class has size Omega(k log k). (C) 2021 Elsevier B.V.

All rights reserved.

Klíčová slova

• Directed graph
• Rainbow
• Caccetta-Haggkvist conjecture
• Directed cycle