Towards the Small Quasi-Kernel Conjecture

Alexandr V. Kostochka, Ruth Luo, Songling Shan

Research output: Contribution to journalArticlepeer-review

Abstract

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).

Original languageEnglish (US)
Article numberP3.49
JournalElectronic Journal of Combinatorics
Volume29
Issue number3
DOIs
StatePublished - 2022

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Towards the Small Quasi-Kernel Conjecture'. Together they form a unique fingerprint.

Cite this