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).
Un graf are o k-colorare dacă și numai dacă are o orientare aciclică⁠(d) pentru care cel mai lung drum⁠(d) are lungime cel mult k; aceasta este teorema Gallai–Hasse–Roy–Vitaver⁠(d) (Nešetřil & Ossona de Mendez 2012).