Polynomial time computability of some graph parameters for superclasses of perfect graphs Online publication date: Wed, 02-May-2012
by Arnaud Pêcher; Annegret K. Wagler
International Journal of Mathematics in Operational Research (IJMOR), Vol. 4, No. 3, 2012
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.
Online publication date: Wed, 02-May-2012
If you are not a subscriber and you just want to read the full contents of this article, buy online access here.Complimentary Subscribers, Editors or Members of the Editorial Board of the International Journal of Mathematics in Operational Research (IJMOR):
Login with your Inderscience username and password:
Want to subscribe?
A subscription gives you complete access to all articles in the current issue, as well as to all articles in the previous three years (where applicable). See our Orders page to subscribe.
If you still need assistance, please email firstname.lastname@example.org