Наредни састанак Семинара биће одржан у уторак, 20. децембра 2022, у сали 301ф Математичког института САНУ са почетком у 14.15.
Предавач: Dunja Pucher, Department of Mathematics, University of Klagenfurt, Austria
Наслов предавања: STRENGTHENING OF THE SEMIDEFINITE RELAXATION FOR GRAPH COLORING PROBLEM
Апстракт: The Lovász Theta function provides a well studied tool to get bounds for the chromatic number of graphs. It is the optimal value of a semidefinite program in matrices of order n having m equality constraints plus possibly some additional sign constraints. Here n denotes the number of vertices and m the number of edges of the underlying graph. We propose a further tightening of this bound using the exact subgraph idea in a new way. Rather than looking at subgraphs with a small number of vertices which should be contained in the respective polytope, we now consider subgraphs with certain structure and require them to be contained in the corresponding polytope. We compare our bounds with relaxations given by Szegedy and Meurdesoif and present computational results.
Напомена: Састанак Семинара се може пратити на даљину преко линка
https://miteam.mi.sanu.ac.rs/asset/YoqHWKALRkRTbK9So
За активно учешће неопходна је регистрација преко линка:
https://miteam.mi.sanu.ac.rs/call/wnz6oyxsQsy29LfJA/MjQ__eH607WeAL9X7IFtUI98xdQQgVkp-ljiEKPPfXr