The maximum k-colorable subgraph problem for chordal graphs.

We discuss the problems of finding maximum and connected maximum k-colorable subgraphs in chordal graphs. We prove that the problems are polynomially solvable when k is fixed and NP-hard when k is not fixed. As a special case, we can find in polynomial time the maximum induced tree and forest of a chordal graph.