We launch a study on the dynamic form of the graph coloring problem proving it to be fixed-parameter tractable with respect to the edit-parameter. This leads us to present a new turbo-charged heuristic for the problem ...