News & Events


Friday, April 21, 2017 - 11:35 to 12:35
SMS Seminal Hall
Samir Shukla
IIT Kanpur
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$.

Contact us

School of Mathematical Sciences

NISERPO- Bhimpur-PadanpurVia- Jatni, District- Khurda, Odisha, India, PIN- 752050

Tel: +91-674-249-4081

Corporate Site - This is a contributing Drupal Theme
Design by WeebPal.