Lexicographic Products and a Conjecture of Hahn and Jackson
J. Adrian Bondy, Xavier Buchwalder, Fréderic Mercier · SIAM Journal on Discrete Mathematics · 2009
The Gallai–Milgram theorem asserts that the vertex set of any digraph with stability number k can be partitioned into k directed paths. Hahn and Jackson conjectured that, for any positive integer k, there exists a digraph with stability number k such that the subdigraph obtained by deleting any $k-1$ directed paths still has stability number k. They established the existence of such digraphs for $k=1,2,3$. Here we construct examples for arbitrarily large values of k.