Let $D=(V,A)$ be a digraph. A vertex set $K\subseteq V$ is a quasi-kernel of $D$ if $K$ is an independent set in $D$ and for every vertex $v\in V\setminus K$, $v$ is at most distance 2 from $K$. In 1974, Chvátal and Lovász proved that every digraph has a quasi-kernel. P. L. Erdős and L. A. Székely in 1976 conjectured that if every vertex of $D$ has a positive indegree, then $D$ has a quasi-kernel of size at most $|V|/2$. This conjecture is only confirmed for narrow classes of digraphs, such as semicomplete multipartite, quasi-transitive, or locally semicomplete digraphs. In this note, we state a similar conjecture for all digraphs, show that the two conjectures are equivalent, and prove that both conjectures hold for a class of digraphs containing all orientations of 4-colorable graphs (in particular, of all planar graphs).
@article{10_37236_11043,
author = {Alexandr V. Kostochka and Ruth Luo and Songling Shan},
title = {Towards the small quasi-kernel conjecture},
journal = {The electronic journal of combinatorics},
year = {2022},
volume = {29},
number = {3},
doi = {10.37236/11043},
zbl = {1498.05115},
url = {http://geodesic.mathdoc.fr/articles/10.37236/11043/}
}
TY - JOUR
AU - Alexandr V. Kostochka
AU - Ruth Luo
AU - Songling Shan
TI - Towards the small quasi-kernel conjecture
JO - The electronic journal of combinatorics
PY - 2022
VL - 29
IS - 3
UR - http://geodesic.mathdoc.fr/articles/10.37236/11043/
DO - 10.37236/11043
ID - 10_37236_11043
ER -
%0 Journal Article
%A Alexandr V. Kostochka
%A Ruth Luo
%A Songling Shan
%T Towards the small quasi-kernel conjecture
%J The electronic journal of combinatorics
%D 2022
%V 29
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/11043/
%R 10.37236/11043
%F 10_37236_11043
Alexandr V. Kostochka; Ruth Luo; Songling Shan. Towards the small quasi-kernel conjecture. The electronic journal of combinatorics, Tome 29 (2022) no. 3. doi: 10.37236/11043
