Parameterized Coloring Problems on Chordal Graphs

摘要

In the precoloring extension problem (PREXT) a graph is given with some of the vertices having a preassigned color and it has to be decided whether this coloring can be extended to a proper coloring of the graph with the given number of colors. Two parameterized versions of the problem are studied in the paper: either the number of precolored vertices or the number of colors used in the precoloring is restricted to be at most k. We show that these problems are polynomial time solvable but W[1]-hard in chordal graphs. For a graph class F, let F + ke (resp. F + kv) denote those graphs that can be made to be a member of F by deleting at most k edges (resp. vertices). We investigate the connection between PREXT in F and the coloring of F + ke, F + ve graphs. Answering an open question of Leizhen Cai, we show that coloring chordal+ke graphs is fixed-parameter tractable.