Let D be a digraph. A kernel K is a subset of vertices that is independent (i.e., all pairs of distinct vertices of K are non-adjacent) and such that, for every vertex v not in K, there exists w ∈ K with (v, w) ∈ A. Kernels were introduced in 1947 by von Neumann and Morgenstern. It is now a central notion in graph theory and has important applications in relations with colorings, perfect graphs, game theory and economics, logic, etc. Chvátal proved that deciding whether a digraph has a kernel is NP-complete and the problem is equally hard for planar digraphs with bounded degree.

Chvátal and Lovász introduced quasi-kernels in 1974. A quasi-kernel in a digraph is a subset Q of vertices that is independent and such that every vertex of the digraph can reach some vertex in Q via a directed path of length at most two. In particular, any kernel is a quasi-kernel. Yet, unlike what happens for kernels, every digraph has a quasi-kernel. Chvátal and Lovász provided a proof of this fact, which can be turned into an easy polynomial-time algorithm.

In 1976, Erdős and Székely conjectured that every sink-free digraph D has a quasi-kernel of size at most |V(D)|/2. This question is known as the small quasi-kernel conjecture. So far, this conjecture is only confirmed for narrow classes of digraphs. In 2008, Heard and Huang showed that every digraph D has two disjoint quasi-kernels if D is a sink-free tournament or a transitive digraph. In particular those graphs respect the small quasi-kernel conjecture. Recently, Kostochka et al. renewed the interest in the small quasi-kernel conjecture and proved that the conjecture holds for orientations of 4-colorable graphs (in particular, for planar graphs).

A split graph is a graph in which the vertices can be partitioned into a clique and an independent set. This class seems to play an important role in the study of small quasi-kernels since the only examples of oriented graphs having no two disjoint quasi-kernels contain the orientation of a split graph constructed by Gutin et al..