Computing clique and chromatic number of circular-perfect graphs in polynomial time
成果类型：
Article
署名作者：
Pecher, Arnaud; Wagler, Annegret K.
署名单位：
Universite de Bordeaux; Centre National de la Recherche Scientifique (CNRS); Universite Clermont Auvergne (UCA)
刊物名称：
MATHEMATICAL PROGRAMMING
ISSN/ISSBN：
0025-5610
DOI：
10.1007/s10107-012-0512-4
发表日期：
2013
页码：
121-133
关键词：
摘要：
A main result of combinatorial optimization is that clique and chromatic number of a perfect graph are computable in polynomial time (Grotschel 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 Lovasz's Theta function.