A note on the Gallai-Roy-Vitaver theorem (Q1849952): Difference between revisions

The main result of the paper states that for any proper colouring \(f\) of a connected graph \(G\) and for any \(r\) distinct colours \(c_1,c_2,\dots,c_r\), there is a path \(v_1,v_2,\dots,v_r\) in \(G\) such that \(f(v_i)=c_i\) for \(1\leq i\leq r\). It extends the well-known Gallai-Roy-Vitaver theorem [\textit{T. Gallai}, Theory of Graphs, Proc. Colloq. Tihany, Hungary 1966, 115-118 (1968; Zbl 0159.54403), \textit{B. Roy}, Rev. Franç. Inform. Rech. Opér. 1, 129-132 (1967; Zbl 0157.31302), \textit{I. Vitaver}, Sov. Math., Dokl. 3, 1687-1688 (1963; Zbl 0126.39302); translation from Dokl. Akad. Nauk SSSR 147, 758-759 (1962)] and its extension proved by \textit{H. Li }[Graphs Comb. 17, 681-685 (2001; Zbl 0989.05042)]. A shorter proof of Li's theorem and a counterexample to his conjecture concerning directed graphs is presented as well.