==Algorithms==Because the problem of testing whether a graph is class 1 is NP-complete, there is no known polynomial time algorithm for edge-coloring every graph with an optimal number of colors.
Поскольку задача проверки, имеет ли граф класс 1, является NP-полной, не известно полиномиального по времени алгоритма рёберной раскраски для любого графа, дающего оптимальную раскраску.