| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4652730 | Electronic Notes in Discrete Mathematics | 2010 | 8 Pages |
Abstract
A main result of combinatorial optimization is that clique and chromatic number of a perfect graph are computable in polynomial time (Grötschel, Lovász and Schrijver 1981). Circular-perfect graphs form a well-studied superclass of perfect graphs. We extend the above result for perfect graphs by showing that clique and chromatic number of a circular-perfect graph are computable in polynomial time as well. The results strongly rely upon Lovász's Theta function.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
