Monday, 15:15 - 15:40 h, Room: H 3005


Denis Cornaz
Strengthening Lovász bound for coloring with a new graph transformation

Coauthor: Meurdesoif Philippe


Let α(G) and χ(G) denote the stability number and the clique-partition number of G, respectively. Using a new graph transformation, one constructs a new operator Φ which associates to any graph parameter β such that α(G) ≤ β(G) ≤ χ(G) for all graphs G, a graph parameter Φβ such that α(G) ≤ Φβ(G) ≤ χ(G) for all graphs G. We prove that ϑ(G) ≤ Φϑ(G) and that Φχf(G) ≤ χf(G) for all graphs~G, where ϑ is Lovász theta function and χf is the fractional clique-partition number. Φϑ is unbounded and numerical experiments show that Φϑ is a significant better lower bound for χ than ϑ.


Talk 1 of the invited session Mon.3.H 3005
"Exact and approximation algorithms on graphs" [...]
Cluster 2
"Combinatorial optimization" [...]


  In particular, Texas Loans Online can cater to the needs of its residents. What can cause long-term use of Canadian Viagra? In the network and other sources of information, there is no reliable data on the long-term use of Viagra and its negative effects on the body.