Further approximations for Aharoni's rainbow generalization of the Caccetta-Häggkvist conjecture (Q2121801)

In this paper, the authors make an important contribution to Aharoni's conjecture, which was proposed as a possible approach to a longstanding conjecture made by Caccetta and Häggkvist. The Caccetta-Häggkvist conjecture states that for positive integers \(n\) and \(k\), a simple digraph \(D\) of order \(n\) satisfying \(\delta^+(v)\ge k\) for every \(v\in V(D)\) contains a directed cycle of length at most \(\lceil n/k\rceil\), where \(\delta^+(v)\) is the outdegree of \(v\) in \(D\). Aharoni generalized this conjecture by transforming it into a problem on edge-coloring of simple undirected graphs. For a simple graph \(G\) and (not necessarily proper) edge-coloring \(b\) of \(G\), a cycle \(C\) of \(G\) is rainbow if every pair of distinct edges in \(C\) receives different colors. The rainbow girth of \(G\) is the length of the shortest rainbow cycle in \(G\). A color class of \(G\) is the set of edges receiving the same color. Aharoni conjectured that if \(b\) uses \(n\) colors and every color class contains \(k\) or more edges, then the rainbow girth of \(G\) is at most \(\lceil n/k\rceil\). Assuming Aharoni's conjecture and given a simple digraph \(D\) of order \(n\) satisfying \(\delta^+(v)\ge k\) for every \(v\in V(D)\), we take an underlying simple graph \(G\) of \(D\) and we color an edge \(uv\) of \(G\) in a color \(u\) if \(uv\) is directed from \(u\) to \(v\) in \(D\). Then a rainbow cycle in \(G\) corresponds to a directed cycle in \(D\) and the Caccetta-Häggkvist conjecture is verified. \par Let \(f(k)\) be the least number \(N\) such that every edge-colored graph \(G\) in which each color class contains \(N\) or more edges contains a rainbow cycle of length at most \(\lceil |G|/k\rceil\). Aharoni's conjecture states \(f(k)\le k\). \textit{P. Hompe} et al. [Discrete Math. 344, No. 5, Article ID 112319, 4 p. (2021; Zbl 1460.05075)] have previously proved \(f(k)=O(k\log k)\). In this paper, they improve the bound to \(f(k)=O(k)\), verifying Aharoni's conjecture in terms of the order of \(f(k)\). \par At the end of the paper, the authors make several observations and propose possible future work. In particular, they point out that in order to solve the Caccetta-Häggkvist conjecture through the setting of Aharoni's conjecture, we have only to find a properly colored cycle of length at most \(\lceil n/k\rceil\) instead of a rainbow cycle. I think it is a simple but nice observation.