TY - JOUR

T1 - Towards the Small Quasi-Kernel Conjecture

AU - Kostochka, Alexandr V.

AU - Luo, Ruth

AU - Shan, Songling

N1 - Funding Information:
∗Supported by NSF grants DMS1600592 and DMS-2153507, and by Arnold O. Beckman Campus Research Board Award RB20003 of the University of Illinois at Urbana-Champaign. †Supported by NSF grant DMS1902808. ‡Supported by NSF grant DMS2153938.
Publisher Copyright:
© The authors.

PY - 2022

Y1 - 2022

N2 - Let D = (V, A) be a digraph. A vertex set K ⊆ V is a quasi-kernel of D if K is an independent set in D and for every vertex v ∈ V \ 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).

AB - Let D = (V, A) be a digraph. A vertex set K ⊆ V is a quasi-kernel of D if K is an independent set in D and for every vertex v ∈ V \ 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).

UR - http://www.scopus.com/inward/record.url?scp=85137317435&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85137317435&partnerID=8YFLogxK

U2 - 10.37236/11043

DO - 10.37236/11043

M3 - Article

AN - SCOPUS:85137317435

SN - 1077-8926

VL - 29

JO - Electronic Journal of Combinatorics

JF - Electronic Journal of Combinatorics

IS - 3

M1 - P3.49

ER -