TY - JOUR
T1 - Fixing improper colorings of graphs
AU - Garnero, Valentin
AU - Junosza-Szaniawski, Konstanty
AU - Liedloff, Mathieu
AU - Montealegre, Pedro
AU - Rzążewski, Paweł
N1 - Publisher Copyright:
© 2017 Elsevier B.V.
PY - 2018/2/8
Y1 - 2018/2/8
N2 - In this paper we consider a variation of a recoloring problem, called the Color-Fixing. Let us have some non-proper r-coloring φ of a graph G. We investigate the problem of finding a proper r-coloring of G, which is “the most similar” to φ i.e., the number k of vertices that have to be recolored is minimum possible. We observe that the problem is NP-complete for any fixed r≥3, even for bipartite planar graphs. Moreover, it is W[1]-hard even for bipartite graphs, when parameterized by the number k of allowed recoloring transformations. On the other hand, the problem is fixed-parameter tractable, when parameterized by k and the number r of colors. We provide a 2n⋅nO(1) 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 fixing number of a graph G. It is the minimum k such that k recoloring transformations are sufficient to transform any coloring of G into a proper one.
AB - In this paper we consider a variation of a recoloring problem, called the Color-Fixing. Let us have some non-proper r-coloring φ of a graph G. We investigate the problem of finding a proper r-coloring of G, which is “the most similar” to φ i.e., the number k of vertices that have to be recolored is minimum possible. We observe that the problem is NP-complete for any fixed r≥3, even for bipartite planar graphs. Moreover, it is W[1]-hard even for bipartite graphs, when parameterized by the number k of allowed recoloring transformations. On the other hand, the problem is fixed-parameter tractable, when parameterized by k and the number r of colors. We provide a 2n⋅nO(1) 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 fixing number of a graph G. It is the minimum k such that k recoloring transformations are sufficient to transform any coloring of G into a proper one.
KW - Fixing number
KW - Parameterized complexity
KW - Reconfiguration
UR - http://www.scopus.com/inward/record.url?scp=85034987250&partnerID=8YFLogxK
U2 - 10.1016/j.tcs.2017.11.013
DO - 10.1016/j.tcs.2017.11.013
M3 - Article
AN - SCOPUS:85034987250
SN - 0304-3975
VL - 711
SP - 66
EP - 78
JO - Theoretical Computer Science
JF - Theoretical Computer Science
ER -