Fixing improper colorings of graphs

In this paper we consider a variation of a recoloring problem, called the Color-Fixing. Let us have some non-proper -coloring of a graph . We investigate the problem of finding a proper -coloring of , which is “the most similar” to , i.e., the number of vertices that have to be recolored is minimum possible. We observe that the problem is NP-complete for any fixed , even for bipartite planar graphs. Moreover, it is -hard even for bipartite graphs, when parameterized by the number of allowed recoloring transformations. On the other hand, the problem is fixed-parameter tractable, when parameterized by and the number of colors.We provide a algorithm for the problem and a linear algorithm for graphs with bounded treewidth. We also show several lower complexity bounds, using standard complexity assumptions. Finally, we investigate the of a graph . It is the minimum such that recoloring transformations are sufficient to transform coloring of into a proper one.