Ориентация рёбер важна для нахождения оптимальной раскраски графа, потому что она влияет на количество цветов, необходимых для правильной раскраски. 5

Согласно теореме Галлаи — Хассе — Роя — Витавера, минимальное число красок, нужных для раскраски любого графа, на единицу больше длины максимального пути в той ориентации графа, в которой эта длина пути минимальна. 5

При раскраске рёбер нужно присвоить цвет каждому ребру так, чтобы любые два смежных ребра имели разные цвета. 4