# coloring infinite vertex transitive graph without large cliques

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?

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.

• It's worth pointing out that (0) the first published proof of this [C. Ward Henson, A family of countable homogeneous graphs, Pacific Journal of Mathematics, Vol. 38, No. 1, 1971], and (1) the technical term for the extension property you mentioned (which evidently is a strengthening of vertex-transitivity, which after all can be seen as extenting a partial isomorphism between 1-vertex-subgraphs) is ultrahomogeneous (Henson called it 'homogeneous', but that usually means something weaker: that there is some automorphism mapping one of the isomorphic subgraphs to the other). Commented Mar 27, 2018 at 13:55

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