























Let $G$ be an abelian group. The main theorem of this paper asserts that there exists a Cayley graph on $G$ with chromatic number $3$ if and only if $G$ is not of exponent $1$, $2$, or $4$. For connected Cayley graphs, we also show that this theorem holds when $G$ is finitely generated. Although motivated by ideas from algebraic topology, our proof may be expressed purely combinatorially. As a by-product, we derive a topological result which is of independent interest. Suppose $X$ is a connected non-bipartite graph, and let $\N(X)$ denote its neighborhood complex. We show that if the fundamental group $π_1(\N(X))$ or first homology group $H_1(\N(X))$ is torsion, then the chromatic number of $X$ is at least $4$. This strengthens a special case of a classical result of Lovász, which derives the same conclusion if $π_1(\N(X))$ is trivial.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。