Я бы сказал слишком общий - раскраска ребер графа суть обычная их пометка в соответствии с тем или иным критерием, разбиение ребер на классы эквивалентности. Понятие "раскраска" в прикладной теории графов встречается чуть ли не на каждом шагу, какая именно раскраска имеется в виду - хз
а подумать ? голова, она не только чтоб в неё есть ;-)
если надо ракрасить рёбра графа G так,
чтобы рёбра одного цета не соприкасались с такими-же,
то
надо посторить граф G` у которого вершины соотв. рёбрам графа G,
и соединяются ребром, если исходные рёбра соприкасались.
Применяем любимый алгоритм раскраски вершин графа G`.
Красим рёбра исходного в соотв.цвета.