Seymour's non-uniform Caccetta–Häggkvist conjecture

About 4 years old · traced to

Let DD be a simple digraph with no sink, meaning no vertex has outdegree zero. Define

ψ(D)=∑v∈V(D)1deg⁡+(v).\psi(D)=\sum_{v\in V(D)}\frac{1}{\deg^+(v)}.

Seymour's non-uniform Caccetta–Häggkvist conjecture. DD contains a directed cycle of length at most

⌈ψ(D)⌉.\left\lceil\psi(D)\right\rceil.

When all outdegrees equal rr, this would imply the Caccetta–Häggkvist conjecture. The conjecture was disproved by Hompe, so it is refuted.

References

Primary source

Katie Clinch, Jackson Goerner, Tony Huynh and Freddie Illingworth, “Notes on Aharoni's rainbow cycle conjecture”, arXiv:2211.07897 (2022).

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.