Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6875648 | Theoretical Computer Science | 2018 | 13 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Valentin Garnero, Konstanty Junosza-Szaniawski, Mathieu Liedloff, Pedro Montealegre, PaweÅ RzÄ
żewski,