You are not logged in | Log in

A topological approach related to Hedetniemi's conjecture

Speaker(s)
Marcin Wrochna
Affiliation
University of Warsaw
Date
April 20, 2017, 12:15 p.m.
Room
room 5870
Seminar
Seminar Algorithms

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".