  


Copositive programming motivated bounds on the stability and the chromatic numbers
Igor Dukanovic (igor.matunimb.si) Abstract: The Lovász theta number of a graph G can be viewed as a semidefinite programming relaxation of the stability number of G. It has recently been shown that a copositive strengthening of this semidefinite program in fact equals the stability number of G. We introduce a related strengthening of the Lovász theta number toward the chromatic number of G, which is shown to be equal to the fractional chromatic number of G. Solving copositive programs is NPhard. This motivates the study of tractable approximations of the copositive cone. We investigate the Parrilo hierarchy to approximate this cone and provide computational simplifications for the approximation of the chromatic number of vertex transitive graphs. We provide some computational results indicating that the Lovász theta number can be strengthened significantly toward the fractional chromatic number of G on some Hamming graphs. Keywords: copositive programming, semidefinite programming, (fractional) chromatic number, Lovász theta number Category 1: Combinatorial Optimization (Graphs and Matroids ) Category 2: Linear, Cone and Semidefinite Programming Citation: To appear in Mathematical Programming, 2008 Download: Entry Submitted: 04/16/2008 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  