A graph has a k-coloring if and only if it has an acyclic orientation for which the longest path has length at most k; this is the Gallai–Hasse–Roy–Vitaver theorem (Nešetřil & Ossona de Mendez 2012).
Egy gráfnak pontosan akkor van k-színezése, ha létezik olyan körmentes irányítása, melyben a leghosszabb út hossza legfeljebb k; ez a Gallai–Hasse–Roy–Vitaver-tétel (Nešetřil & Ossona de Mendez 2012).