Существуют алгоритмы полиномиального времени, создающие оптимальную раскраску двудольных графов и раскраску простого не двудольного графа с числом цветов {\Delta}+1.
Однако, в общем случае, задача поиска оптимальной рёберной раскраски NP-полна и самый быстрый из известных алгоритмов для неё работает за экспоненциальное время.
Рёберная раскраска
Итак, можно найти раскраску в Delta + 1 цветов за полиномиальное время (что тоже может оказаться совсем не быстро). Но чтобы доказать, что не существует раскраски (иначе, найти ее) ровно в Delta цветов, необходимо решить NP-полную задачу за экспоненциальное время.
(Delta - максимальная степень вершины).