Kostochka–Luo–Shan conjecture for quasi-kernels and sinks
Kostochka–Luo–Shan conjecture for quasi-kernels and sinks
Let be a digraph, let be the set of sinks of , and let be the set of in-neighbors of vertices in . Let . A quasi-kernel of is an independent subset of vertices such that the shortest path from every vertex to it has length at most two.
Kostochka–Luo–Shan conjecture. Every digraph has a quasi-kernel of size at most
The case was proposed by Kostochka, Luo, and Shan, and the source states that this case is equivalent to the small quasi-kernel conjecture. The displayed formulation is presented as a more general conjecture, whose status is not resolved in the supplied text.
Sources & referencesView supporting material
Primary source
Hélène Langlois, Frédéric Meunier, Romeo Rizzi, Stéphane Vialette and Yacong Zhou, “Quasi-kernels in split graphs”, arXiv:2312.15519 (2024).
Additional references
2 papers in this index state this conjecture (2023). The statement above is taken from the most recent of them; the others are arXiv:2307.04112.
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.