Трудно тебе будет.
1. Находишь путь.
2. Из этого пути поочередно удаляешь по ребру и строишь путь в графе без ребра. Один из вариантов (или несколько) будут кратчайшими. Если несколько - задача решена.
3. Если нет - ну ты понел...
Это жадный алгоритм раскраски.
При удачном раскладе даёт оптимальную по числу цветов раскраску, но обычно - нет.
Точное решение достигается, увы, полным перебором.