





















The neighborhood complex $\N(G)$ of a graph $G$ were introduced by L. Lov{á}sz in his proof of Kneser conjecture. He proved that for any graph $G$, \begin{align} \label{abstract} χ(G) \geq conn(\N(G))+3. \end{align} In this article we show that for a class of exponential graphs the bound given in (\ref{abstract}) is sharp. Further, we show that the neighborhood complexes of these exponential graphs are spheres up to homotopy. We were also able to find a class of exponential graphs, which are homotopy test graphs. Hedetniemi's conjecture states that the chromatic number of the categorical product of two graphs is the minimum of the chromatic number of the factors. Let $M(G)$ denotes the Mycielskian of a graph $G$. We show that, for any graph $G$ containing $M(M(K_n))$ as a subgraph and for any graph $H$, if $χ(G \times H) = n+1$, then $\min\{χ(G), χ(H)\} = n+1$. Therefore, we enrich the family of graphs satisfying the Hedetniemi's conjecture.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。