Coloring a graph using Depth first traversal

Question

I know that for coloring graph nodes, backtracking/brute force is a common solution. But I was wondering if using DFS I can also achieve a solution ?

Backtracking gives you the opportunity to go back and try other color possibility in order to paint all the nodes with N colors

DFS will start from one node and color it, then jump to its neighbor and color it in different color than its neighbors etc ...

I did a search about using this method but I didn't find an algorithm that uses this.

Question: Is using DFS possible for coloring graph nodes. If yes, is it more efficient than backtracking ?

Thank you

Answer 1

I believe there is some confusion when comparing backtracking and DFS wrt vertex coloring. DFS traversal for a graph gives full enumeration of its vertices in a sequence related to its structure. It does not, however, constitute a full enumeration for the vertex coloring problem, which would require taking into account the possible colors of the vertices.

Thus, if I understand correctly, what you have implemented is a greedy heuristic coloring for a graph directed by DFS. On the other hand, a backtracking/brute force solution as you name it (such as [Randall-Brown 72]) will provide an exact solution for the minimum coloring problem since it considers every possible vertex coloring. Note that DFS traversal could be used to sort the vertices initially (topological sort) and feed that order to the exact solver.