coloring infinite vertex transitive graph without large cliques

Question

Let $G$ be an infinite vertex-transitive graph (this means that for every $u,w \in V(G)$ there exists an automorphism $\tau$ of $G$ such that $\tau(u) = v$). We assume that $G$ is undirected, and does not have loops.

Suppose that there exists some $B \in \mathbb{N}$ such that $G$ does not contain a clique of size $B$.

Does $G$ necessarily have a proper coloring which uses only a finite number of colors?

Answer 1

Apart of the specific Mycielski-like construction from the article in Dominic's answer, we may take the universal triangle free-graph, which satisfies the following conditions:

(i) $G$ has countable number of vertices;

(ii) $G$ does not contain triangles;

(iii) for any finite set $V_0$ of vertices of $G$ and any independent subset $V_1\subset V_0$ there exists a vertex $u\notin V_0$ in $G$ such that $N(u)\cap V_0=V_1$. Here $N(u)$ denotes, as usual, the set of neighbours of $u$.

It is easy to achieve this by inductive procedure, and also it is easy to check that this graph is highly transitive (any partial isomorphisms between finite subgraphs may be extended to a genuine automorphism of the whole $G$). Also $G$ contains all finite triangle-free graphs (the vertices of such a graph may be constructed consequentially). Thus $G$ has infinite chromatic number, since the finite triangle-free subgraphs may have arbitrarily large chromatic number.

Answer 2

No - there are triangle-free, vertex transitive graphs of infinite chromatic number, see for instance this article.