Nie jesteś zalogowany | Zaloguj się

A topological approach related to Hedetniemi's conjecture

Prelegent(ci)
Marcin Wrochna
Afiliacja
University of Warsaw
Termin
20 kwietnia 2017 12:15
Pokój
p. 5870
Seminarium
Seminarium "Algorytmika"

Hedetniemi's 50 years old conjecture states that the chromatic number of the tensor product of graphs G,H is the minimum of the chromatic numbers of G and H. The conjecture has many interesting connections with graph theory, especially with graph homomorphisms, where we consider more generally a property called 'multiplicativity'. Hedetniemi's conjecture is then that all cliques are multiplicative; still, the only known case is the 3-clique. I will give a more general proof of this, yielding that all graphs not containing 4-cycles as subgraphs are multiplicative. The proof is based on viewing graphs as topological spaces, as I will explain from basics, and suggests some deeper connections of topology with combinatorics. No prior knowledge assumed beyond "chromatic number".