The edge-coloring problem asks whether it is possible to color the edges of a given graph using at most different colors, for a given value of , or with the fewest possible colors.
Задача рёберной раскраски задаётся вопросом, можно ли раскрасить рёбра заданного графа максимум в formula_1 различных цветов для заданного значения formula_1 или для минимального возможного числа цветов.