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 - Funding Information:
Supported by ERC Starting Grant PARAMTIGHT (No. 280152).
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 -