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

---