The large-quasikernel structural conjecture

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 AV(D)A\subseteq V(D) such that D[A]D[A] is acyclic and

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

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

deg+(y)V(D)1/21.\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.

Sources & referencesView supporting material

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.