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

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

ψ(D)=vV(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.

Sources & referencesView supporting material

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.