A generalization of the Gallai-Roy theorem (Q5956104)

For a digraph \(D\), let \(\Psi(D)\) be the set of all vertices which are connected by a directed path to all other vertices of \(D\). Denoting by \(p(v)\) the number of vertices on a longest directed path from \(v\), let \(\psi(D)\) be the minimum value of \(p(v)\) taken over the vertices of \(\Psi(D)\). In the paper it is shown that the chromatic number of any digraph is bounded from above by \(\psi(D)\). This strengthens the classical Gallai-Roy theorem which claims that a digraph with chromatic number \(k\) contains a directed path of at least \(k\) vertices. For undirected graphs the author answers a question of Fajtlowicz by showing that for any \(k\)-colouring of a graph \(G\) with chromatic number \(k\) there exists a path starting at any vertex of \(G\) and representing all \(k\) colours.