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

Arnaud Pêcher and Annegret K. Wagler

International Journal of Mathematics in Operational Research, 2012, vol. 4, issue 3, 263-275

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. (search for similar items in EconPapers)
Date: 2012
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.inderscience.com/link.php?id=46687 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ids:ijmore:v:4:y:2012:i:3:p:263-275

Access Statistics for this article

More articles in International Journal of Mathematics in Operational Research from Inderscience Enterprises Ltd
Bibliographic data for series maintained by Sarah Parker ().