Computing clique and chromatic number of circular-perfect graphs in polynomial time |
| |
Authors: | Arnaud Pêcher Annegret K Wagler |
| |
Institution: | 1. Laboratoire Bordelais de Recherche Informatique (LaBRI)/INRIA Sud-Ouest, Université de Bordeaux, 351 cours de la Libération, 33405, Talence, France 2. Laboratoire d’Informatique, de Modélisation et d’Optimisation des Systèmes (LIMOS)/CNRS, Université Blaise Pascal (Clermont-Ferrand II), BP 10125, 63173, Aubière Cedex, France
|
| |
Abstract: | A main result of combinatorial optimization is that clique and chromatic number of a perfect graph are computable in polynomial time (Grötschel et al. in Combinatorica 1(2):169–197, 1981). Perfect graphs have the key property that clique and chromatic number coincide for all induced subgraphs; we address the question whether the algorithmic results for perfect graphs can be extended to graph classes where the chromatic number of all members is bounded by the clique number plus one. We consider a well-studied superclass of perfect graphs satisfying this property, the circular-perfect graphs, and show that for such graphs both clique and chromatic number are computable in polynomial time as well. In addition, we discuss the polynomial time computability of further graph parameters for certain subclasses of circular-perfect graphs. All the results strongly rely upon Lovász’s Theta function. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|