Rainbow Caccetta–Häggkvist conjecture for edge-set families

Let GG be an undirected graph, and let F1,F2,,FnF_1,F_2,\ldots,F_n be sets of edges in GG. For a family of edge sets, let rg(F1,,Fn)rg(F_1,\ldots,F_n) denote the length of its shortest rainbow cycle. Rainbow Caccetta–Häggkvist conjecture. If each FiF_i has size at most kk, then

rg(F1,F2,,Fn)nk.rg(F_1,F_2,\ldots,F_n)\leq \big\lceil \frac{n}{k}\big\rceil.

This is a rainbow analogue of the Caccetta–Häggkvist conjecture, relating prescribed edge colours to short rainbow cycles. The paper presents it as a conjecture suggested by the first author; the stated general form remains open.

Sources & referencesView supporting material

Primary source

Ron Aharoni, Eli Berger, Maria Chudnovsky, He Guo and Shira Zerbib, “Non-uniform degrees and rainbow versions of the Caccetta-Häggkvist conjecture”, arXiv:2110.11183 (2022).

Additional references

2 papers in this index state this conjecture (2018–2021). The statement above is taken from the most recent of them; the others are arXiv:1804.01317.

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.