Authors: Nicola Apollonio, Massimiliano Caramia
Addresses: Istituto per le Applicazioni del Calcolo, M. Picone, Via G. Amendola, 122/D, Bari 70126, Italy. ' Dipartimento di Ingegneria dell'Impresa, University of Rome 'Tor Vergata', Via del Politecnico 1, Rome 00133, Italy
Abstract: 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 Yannakakis and Gavril and independently of Corneil and Fonlupt, 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.
Keywords: greedy algorithms; perfect graphs; vertex colouring; q-colourable; subgraphs.
International Journal of Mathematics in Operational Research, 2010 Vol.2 No.1, pp.1 - 16
Published online: 01 Dec 2009 *Full-text access for editors Access for subscribers Purchase this article Comment on this article