Parameterized coloring problems on chordal graphs

In the precoloring extension problem (PREXT) a graph is given with some of the vertices having preassigned colors 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 for chordal graphs these problems are polynomial-time solvable for every fixed k, but W[1]-hard if k is the parameter. 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 (with the two parameters defined above) and the coloring of F + ke, F + kv graphs (with k being the parameter). Answering an open question of Leizhen Cai [Parameterized complexity of vertex colouring, Discrete Appl. Math. 127 (2003) 415–429], we show that coloring chordal + ke graphs is fixed-parameter tractable.

Authors

• Dániel Marx

Keywords

• Coloring
• Precoloring extension
• Parameterized complexity
• Chordal graphs
• Interval graphs