Strong 2-kernel size bound in split digraphs
Open question on strong 2-kernels in split digraphs · arXiv:2409.05039
Status open high confidence
The source paper (Theorem 2.4) proves that every split digraph with no sources has a standard 2-kernel of size at most |G|/2, resolving the Erdős–Székely conjecture for this class. The open question asks whether the size bound survives when the 2-kernel is required to be strong — i.e., every vertex v in the tournament part T is either 1-covered by some vertex of K, or 2-covered by some vertex of K ∩ T. No follow-up work addressing this stronger variant was found in the indexed literature. The conjecture is recent (posted September 2024) and a targeted web search returns no evidence of resolution.
Reviewer notes. No follow-up found on this specific open question. The source paper was published in The Electronic Journal of Combinatorics (v33i1p32, 2025). The main 2-kernel result (Theorem 2.4) is fully established; the strong 2-kernel variant asks whether the additional covering requirement for vertices in the tournament part T still allows a kernel of size at most |G|/2. The authors explicitly note they do not know the answer.
Context
The paper proves (Theorem 2.4) that every split digraph with no sources has a 2-kernel of size at most $|G|/2$. A 2-kernel $K$ is called strong if for every vertex $v$ in the tournament part $T$, either some vertex of $K$ 1-covers $v$, or some vertex of $K \cap T$ 2-covers $v$. The authors note in passing that they do not know whether the size bound survives under this strengthening.
Notes. Stated as a parenthetical remark inside the proof section: 'We do not know whether 1.2 remains true if we ask for a strong 2-kernel of size at most |G|/2.' No labelled theorem environment.
Source paper
Distant digraph domination
Tung Nguyen, Alex Scott, Paul Seymour · 2024-09-08
https://arxiv.org/abs/2409.05039
PDF source