Title: On the maximum q-colourable induced subgraph problem in perfect graphs

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.

DOI: 10.1504/IJMOR.2010.029686

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 Full-text access for subscribers Purchase this article Comment on this article