Fixing improper colorings of graphs

Garnero, Valentin; Junosza-Szaniawski, Konstanty; Liedloff, Mathieu; Montealegre, Pedro; Rzazewski, Pawel

Abstract

In this paper we consider a variation of a recoloring problem, called the Color-Fixing. Let us have some non-proper r-coloring phi of a graph G. We investigate the problem of finding a proper r-coloring of G, which is "the most similar" to phi, 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 2(n) . n(O(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 facing 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. (C) 2017 Elsevier B.V. All rights reserved.

Más información

Título según WOS: ID WOS:000424959100006 Not found in local WOS DB
Título de la Revista: THEORETICAL COMPUTER SCIENCE
Volumen: 711
Editorial: ELSEVIER SCIENCE BV
Fecha de publicación: 2018
Página de inicio: 66
Página final: 78
DOI:

10.1016/j.tcs.2017.11.013

Notas: ISI