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

---