+91-674-249-4082

Submitted by klpatra on 11 April, 2017 - 12:31

Date/Time:

Friday, April 21, 2017 - 11:35 to 12:35

Venue:

SMS Seminal Hall

Speaker:

Samir Shukla

Affiliation:

IIT Kanpur

Title:

Connectedness of Certain Graph Coloring Complexes

Abstract: The Kneser Conjecture was proved by Lovasz, using the Borsuk Ulam Theorem.
Lovasz introduced the notion of a simplicial complex called the neighborhood complex
for a graph $G$ with an aim of estimating the chromatic number of any graph by the
connectivity of its neighborhood complex. This notion was generalised to
construct another simplicial complex called the Hom complex, Hom$(G,H)$ for any two
graphs G and H. The connectedness of the Hom complex is related to the chromatic
numbers of the graphs G and H via the Lovasz Conjecture. In this talk, we consider the regular
bipartite graphs of the type $K_2 \times K_m$ and prove that the connectedness of the complex
Hom$(K_2 \times K_m , K_n )$ is $n- m -1 $ if $n \geq m$ and $n - 3$ in the
other cases. Further, we show that Hom$(K_2 \times K_m, K_n)$ is homotopic to $S^{n-2}$, if $3 \leq n < m$.

**School of Mathematical Sciences**

NISER, PO- Bhimpur-Padanpur, Via- Jatni, District- Khurda, Odisha, India, PIN- 752050

Tel: +91-674-249-4081

Corporate Site - This is a contributing Drupal Theme

Design by WeebPal.

Design by WeebPal.