10.30 am, Seminar Hall
Topological connectivity of graph coloring complexes of certain product graphs
Samir Shukla
ISI, Bengaluru.
07-02-18

---

Abstract

In 1978 Lovasz gave a proof of Kneser's conjecture in graph theory using topological methods. Since then applying topological techniques to solve problems in graph theory and combinatorics has been very fruitful.

The general strategy involves first associating a simplicial complex to a graph and then relating some topological property like connectivity of this complex to the graphical property like chromatic number of the graph.

In his proof of Kneser's conjecture, Lovasz introduced neighborhoood complex of a graph and later generalized it to a polyhedral complex called hom complex for two graphs G and H.

In this talk I shall focus on certain product graphs and their associated hom complexes. Using discrete Morse theory I will establish the topological connectivity of these complexes.

In a special case these complexes have the same homotopy type as that of a sphere of certain dimension. This is a joint work with Nandini Nilakantan.