Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
Fixing Improper Colorings of Graphs
verfasst von : Konstanty Junosza-Szaniawski, Mathieu Liedloff, Paweł Rzążewski
Erschienen in: SOFSEM 2015: Theory and Practice of Computer Science
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In this paper we consider a variation of a recoloring problem, called the
r
-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, but is Fixed Parameter Tractable (FPT), when parametrized by the number of allowed transformations
k
. We provide an
$\mathcal{O}^*(2^n)$
algorithm for the problem (for any fixed
r
) and a linear algorithm for graphs with bounded treewidth. Finally, we investigate the
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.