The large-quasikernel structural conjecture

About 2 years old · traced to

Let DD be a finite digraph. A quasikernel is an independent set from which every vertex is reachable by a directed path of length at most 22. For a vertex yy, let deg⁡+(y)\deg^+(y) denote its out-degree.

Large-quasikernel structural conjecture. Every digraph DD either contains a subset A⊆V(D)A\subseteq V(D) such that D[A]D[A] is acyclic and

∣A∣≥∣V(D)∣1/2,|A|\ge |V(D)|^{1/2},

or contains a vertex y∈V(D)y\in V(D) that belongs to some quasikernel and satisfies

deg⁡+(y)≥∣V(D)∣1/2−1.\deg^+(y)\ge |V(D)|^{1/2}-1.

If true, this structural dichotomy would improve the paper's lower bounds on the size of the closed out-neighborhood of a quasikernel. The source presents it as a conjectural route toward the Large Quasikernel Conjecture.

References

Primary source

Sam Spiro, “Generalized Quasikernels in Digraphs”, arXiv:2404.07305 (2024).

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.