On the polynomial time computability of the circular-chromatic number for some superclasses of perfect graphs |
| |
| Affiliation: | 1. Division of Computational Mechanics, Ton Duc Thang University, Ho Chi Minh City, Viet Nam;2. Faculty of Civil Engineering, Ton Duc Thang University, Ho Chi Minh City, Viet Nam;3. Institute of Structural Mechanics, Bauhaus Universität-Weimar, 99423 Weimar, Germany;1. Department of Mechanical Engineering, Sakarya University, 54187 Sakarya, Turkey;2. Department of Mechanical Engineering, Bilecik Şeyh Edebali University, 11210 Bilecik, Turkey;1. National Textile University, National Centre for Composite Materials, Faisalabad, Pakistan;2. Normandie University, UNIHAVRE, CNRS, LOMC, Le Havre, France |
| |
| Abstract: | A main result in combinatorial optimization is that clique and chromatic number of a perfect graph are computable in polynomial time (Grötschel, Lovász and Schrijver 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 the (weighted) circular-clique and circular-chromatic number of a circular-perfect graph are computable in polynomial time. In this paper, we show the polynomial time computability of these two graph parameters for some super-classes of perfect graphs with the help of polyhedral arguments. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
