Paths and stability number in digraphs (Q2380212)

Summary: The Gallai-Milgram theorem says that the vertex set of any digraph with stability number \(k\) can be partitioned into \(k\) directed paths. In 1990, {ıG. Hahn} and \textit{B. Jackson} [``A note concerning paths and independence number in digraphs,'' Discrete Math. 82, No.\,3, 327--329 (1990; Zbl 0701.05020)] conjectured that this theorem is best possible in the following strong sense. For each positive integer \(k\), there is a digraph \(D\) with stability number \(k\) such that deleting the vertices of any \(k - 1\) directed paths in \(D\) leaves a digraph with stability number \(k\). In this note, we prove this conjecture.