Title: Polynomial time computability of some graph parameters for superclasses of perfect graphs

Authors: Arnaud Pêcher; Annegret K. Wagler

Addresses: Laboratoire Bordelais de Recherche Informatique (LaBRI), University of Bordeaux, 351 cours de la Libération, 33405 Talence, France. ' Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), University Blaise Pascal (Clermont-Ferrand II), 63173 Aubière Cedex, France

Abstract: A main result in combinatorial optimisation is that clique and chromatic number of a perfect graph are computable in polynomial time (Grötschel et al., 1981). The circular-clique and circular-chromatic number are well-studied refinements of these graph parameters, and circular-perfect graphs form the corresponding superclass of perfect graphs. So far, it is unknown whether clique, circular-clique, circular-chromatic and chromatic numbers of a circular-perfect graph are computable in polynomial time. In this paper, we show the polynomial time computability of these graph parameters for some classes of circular-perfect graphs with the help of polyhedral arguments.

Keywords: circular-perfect graphs; polytope; circular clique; polynomial time; combinatorial optimisation; perfect graphs; circular chromatic.

DOI: 10.1504/IJMOR.2012.046687

International Journal of Mathematics in Operational Research, 2012 Vol.4 No.3, pp.263 - 275

Published online: 02 May 2012 *

Full-text access for editors Access for subscribers Purchase this article Comment on this article