On the maximum \(q\)-colourable induced subgraph problem in perfect graphs (Q964478)

Summary: Given a non-negative integer \(q\), the maximum \(q\)-colourable induced subgraph (MCS) problem asks for an induced subgraph of maximum order among those that are \(q\)-colourable. By a result of \textit{M. Yannakakis} and \textit{F. Gavril} [``The maximum k-colorable subgraph problem for chordal graphs,'' Inf. Process. Lett. 24, 133--137 (1987; Zbl 0653.68070)] and independently of \textit{D.G. Corneil} and \textit{J. Fonlupt} [``The complexity of generalized clique covering,'' Discrete Appl. Math. 22, No.\,2, 109--118 (1989; Zbl 0685.68046)], the MCS is NP-Complete even if restricted to the class of split graphs. In this paper, we investigate the approximability of the MCS problem in the class of perfect graphs.