0
$\begingroup$

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?

$\endgroup$

2 Answers 2

6
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ 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). $\endgroup$ Mar 27, 2018 at 13:55
4
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.