2016/07/23 by Valentin Garnero, Konstanty Junosza-Szaniawski, Garnero, Valentin +7
Computer Science · Mathematics · #Advanced Graph Theory Research #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1607.06911
openalex publication_date 2016/07/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 r ≥ 3, even for bipartite planar graphs. On the other hand, the problem is fixed-parameter tractable, when parameterized by the number of allowed transformations k. We provide an 2n ⋅ nO(1) algorithm for the problem (for any fixed r) and a linear algorithm for graphs with bounded treewidth. We also show several lower complexity bounds, using standard complexity assumptions. Finally, we investigate the \em fixing number of a graph G. It is the maximum possible distance (in the number of transformations) between some non-proper coloring of G and a proper one.