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? 



coloring infinite vertex transitive graph without large cliques
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.


