A variable version of the quasi-kernel conjecture

Jiangdong Ai¹ ; Xiangzhou Liu ; Fei Peng

¹Nankai University

The electronic journal of combinatorics, Tome 32 (2025) no. 2

Résumé

A quasi-kernel of a digraph $D$ is an independent set $Q$ such that every vertex can reach $Q$ in at most two steps. A 48-year conjecture made by P.L. Erdős and Székely, known as the small QK conjecture, says that every sink-free digraph contains a quasi-kernel of size at most $n/2$. Recently, Spiro posed the large QK conjecture, that every digraph contains a quasi-kernel $Q$ such that $|N^-[Q]|\geq n/2$, and showed that it follows from the small QK conjecture. In this paper, we establish that the large QK conjecture implies the small QK conjecture with a weaker constant. We also show that the large QK conjecture is equivalent to a sharp version of it, answering affirmatively a question of Spiro. We formulate variable versions of these conjectures, which are still open in general. Not many digraphs are known to have quasi-kernels of size $(1-\alpha)n$ or less. We show that digraphs with bounded dichromatic number have quasi-kernels of size at most $(1-\alpha)n$, by proving a stronger statement.

Détail

DOI : 10.37236/13653

Classification : 05C69, 05C20
Mots-clés : large QK conjecture