Spiro's bipartite quasikernel improvement conjecture

Let DD be a source-free bipartite digraph, meaning that every vertex has a nonempty set of external in-neighbors. A quasikernel of DD is an independent set QV(D)Q\subseteq V(D) such that every vertex vV(D)v\in V(D) satisfies distD(Q,v)2\operatorname{dist}_D(Q,v)\le 2. Spiro's bipartite quasikernel improvement conjecture. There exists ε>0\varepsilon>0 such that, if DD has no directed 22-cycle and no directed 44-cycle, then DD has a quasikernel QQ with

Q(12ε)V(D).|Q|\le \left(\frac12-\varepsilon\right)|V(D)|.

Spiro proved a strict improvement over the half bound for the relevant bipartite digraphs apart from the excluded cycle cases. The conjecture asks whether the improvement can be made uniform by a fixed positive ε\varepsilon; it remains open.

Sources & referencesView supporting material

Primary source

Zejun Huang and Chenxi Yang, “Three Results on Generalized Quasikernels in Digraphs”, arXiv:2607.09031 (2026).

Additional references

8 papers in this index state this conjecture (2020–2026). The statement above is taken from the most recent of them; the others are arXiv:2606.16571, arXiv:2606.16971, arXiv:2406.04887, arXiv:2404.07305, arXiv:2312.15519, arXiv:2110.00789, arXiv:2001.04003.

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.