Fixing improper colorings of graphs

Valentin Garnero, Konstanty Junosza-Szaniawski, Mathieu Liedloff, Pedro Montealegre, Paweł Rzążewski

Research output: Contribution to journalArticlepeer-review

4 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)66-78
Number of pages13
JournalTheoretical Computer Science
Volume711
DOIs
StatePublished - 8 Feb 2018

Keywords

  • Fixing number
  • Parameterized complexity
  • Reconfiguration

Fingerprint

Dive into the research topics of 'Fixing improper colorings of graphs'. Together they form a unique fingerprint.

Cite this