Kostochka–Luo–Shan conjecture for quasi-kernels and sinks

Let DD be a digraph, let S(D)S(D) be the set of sinks of DD, and let N(S(D))N^-(S(D)) be the set of in-neighbors of vertices in S(D)S(D). Let α12\alpha\geqslant \frac{1}{2}. A quasi-kernel of DD 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 DD has a quasi-kernel of size at most

α(V(D)+S(D)N(S(D))).\alpha\bigl(|V(D)|+|S(D)|-|N^-(S(D))|\bigr).

The case α=12\alpha=\frac{1}{2} 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

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.