Spiro's bipartite quasikernel improvement conjecture
Spiro's bipartite quasikernel improvement conjecture
Let be a source-free bipartite digraph, meaning that every vertex has a nonempty set of external in-neighbors. A quasikernel of is an independent set such that every vertex satisfies . Spiro's bipartite quasikernel improvement conjecture. There exists such that, if has no directed -cycle and no directed -cycle, then has a quasikernel with
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 ; 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.