Сейчас пытаюсь делать так. Строю дополнительный граф, в котором вершины соответсвуют ребрам оригинального(=исходного) графа. Вершины графа соеденены ребрами только тогда, когда соответсвующие им ребра исходного графа инцедентнтны друг-другу. Потом произвоодится расскраска вершин этого графа. Для расскраски графа надо выделить минимальное число внутренне устойчевых множеств.
Если есть другие идеи решения поставленной изначально задачи, с радостью выслушаю их.
