Application of the Lovász-Schrijver M+ operator to graph coloring
Federico Battista  1, *@  , Fabrizio Rossi  2@  , Stefano Smriglio  2@  
1 : Università di Roma “Sapienza”
2 : Università degli Studi dell'Aquila
* : Corresponding author

Computing strong lower bounds for the chromatic number of a graph is a well-researched topic. A reference lower bound is represented by the Lovász theta number, which can be computed via semidefinite programing (SDP). Further relaxations have been investigated, by adding linear inequalities to the Lovász relaxation. These experiences show that achieving lower bounds over the fractional chromatic number is a hard task. We present a new SDP relaxation obtained by the application of the Lovász-Schrijver lifting operator to a compact ILP formulation. Computational experiments on small graphs shows that this relaxation yields lower bounds which can lie above the fractional chromatic number.



  • Poster
Online user: 3 Privacy
Loading...