Sam Spiro, Rutgers University

Abstract

Given a digraph $D$, we say that a set of vertices $Qsubseteq V(D)$ is a quasikernel if $Q$ is an independent set and if every vertex of $D$ can be reached from $Q$ by a path of length at most 2.  The Small Quasikernel Conjecture of P.L. ErdH{o}s and Sz'ekely from 1976 states that every $n$-vertex source-free digraph $D$ contains a quasikernel of size at most $frac{1}{2}n$.  Despite being posed nearly 50 years ago, very little is known about this conjecture, with the only non-trivial upper bound of $n-frac{1}{4}sqrt{nlog n}$ being proven very recently by ourself.  We discuss this together with a number of other related results and open problems around the Small Quasikernel Conjecture.

See: https://sites.math.rutgers.edu/~kmg326/GCS/GCS.html