Elisabeth Gaar, Vizing's Conjecture: From Graph Theory to Semidefinite Programming via an Algebraic Model

 
Abstract: 
In 1968 Vizing conjectured, that the product of domination number of two 
graphs is always smaller or equal to the domination number of the 
product graph. Today, we still don't know whether this conjecture is 
true or not. 
In this talk we will investigate a completely new way of tackling 
Vizing's conjecture. First we will build an algebraic model of the 
conjecture with some parameters. Then we will translate Vizing's 
conjecture for these parameters into the question of whether a specific 
polynomial is nonnegative over a specific ideal. Then we will do another 
reformulation to the question of whether a specific polynomial is a 
sum-of-squares polynomial and discuss how we can use semidefinite 
programming to answer these kind of questions. 
Eventually we will discuss our obtained results, which provide a proof 
of concept of our new method to tackle Vizing's conjecture. 

 
Vljudno vabljeni! 

 
Roman Drnovšek in Primož Moravec