Given a cardinal $\kappa > 2$, is there a triangle-free vertex-transitive graph $G=(V,E)$ with chromatic number $\chi(G) = \kappa$?
$\begingroup$
$\endgroup$
3
-
1$\begingroup$ Do you know the answer if you remove vertex-transitive condition? $\endgroup$Wojowu– Wojowu2026-04-30 08:18:24 +00:00Commented yesterday
-
$\begingroup$ The Henson graphs are $K_n$-free ultraomogeneous countable graphs with countable chromatic number. By Löwenheim-Skolem we can produce ultrahomogeneous $K_n$-free graphs in all cardinalities, but it is unclear to me what's their chromatic number $\endgroup$Alessandro Codenotti– Alessandro Codenotti2026-04-30 12:42:01 +00:00Commented yesterday
-
2$\begingroup$ @AlessandroCodenotti thanks. I edited (it was strange to type a title without the most important and specific condition). $\endgroup$YCor– YCor2026-04-30 13:12:12 +00:00Commented yesterday
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
4
Yes.
For finite $\kappa=n\geq 3$, take the Kneser graph $G=KG(3n-4,n-1).$
Now let $\kappa$ be infinite. By a theorem of Erdős and Rado (cited here), there is a triangle-free graph $H$ of cardinality $\kappa$ with $\chi(H)=\kappa.$ Denote the vertex set of $H$ by $W$.
We now turn this into a vertex-transitive example. Let $A=\mathbb F_2^{W}$ be the Boolean group of finite subsets of $W$, with addition given by symmetric difference. For each $w\in W$, write $e_w$ for the corresponding basis vector. Define a Cayley graph $G$ on $A$ by putting $xy\in G \quad\Longleftrightarrow\quad x+y=e_u+e_v$ for some edge $uv\in H$.
Since $G$ is a Cayley graph, it is vertex-transitive and by construction it is also triangle-free if $H$ was triangle-free. Also, $H$ is obviously a subset of $G$, so we are done.
The proof was done by ChatGPT 5.4 Thinking, I edited the solution.
-
1$\begingroup$ Yes, that error is due to my rewriting of the solution. $\endgroup$domotorp– domotorp2026-05-01 03:33:36 +00:00Commented 12 hours ago
-
1$\begingroup$ @bof Because $|A|=\kappa$. $\endgroup$Emil Jeřábek– Emil Jeřábek2026-05-01 07:57:53 +00:00Commented 7 hours ago
-
$\begingroup$ What are the downvotes for? The acknowledgment at the end, is that it? $\endgroup$bof– bof2026-05-01 09:11:18 +00:00Commented 6 hours ago
-
$\begingroup$ My apologize for this question: I am just curious, why wasn’t ChatGPT 5.5 Pro used here instead of 5.4 Thinking? $\endgroup$Dang Dang– Dang Dang2026-05-01 10:12:25 +00:00Commented 5 hours ago
$\begingroup$
$\endgroup$
0
Here is a very simple construction of a triangle-free vertex-transitive graph whose chromatic number is greater than a given cardinal number $\kappa$.
Let $S$ be a totally ordered set of cardinality $|S|\gt2^\kappa$. Following Erdős and Hajnal we construct a triangle-free graph $G=(V,E)$ of chromatic number $\chi(G)\gt\kappa$ as follows: $V=\{(a,b)\in S\times S:a\lt b\}$ and $E=\{\{(a,b),(b,c)\}\in\binom V2:a\lt b\lt c\}$. Plainly $G$ is triangle-free.
To see that $\chi(G)\gt\kappa$, consider any map $f:V\to\kappa$. Now define a map $F:S\to\mathcal P(\kappa)$ by setting $F(a)=\{f(a,b):a\lt b\in S\}$. Since $|S|\gt2^\kappa$, there is a vertex $(a,b)\in V$ with $F(a)=F(b)$. Since $f(a,b)\in F(a)=F(b)$, there is a vertex $(b,c)\in V$ with $f(b,c)=f(a,b)$, so $f$ is not a proper coloring.
Any order-isomorphism of $S$ induces an automorphism of the graph $G$. Erdős and Hajnal originally used this construction with a well-ordered set $S$; however, by letting $S$ be an ordered field, we get a vertex-transitive graph $G$.
$\begingroup$
$\endgroup$
You already have a perfectly fine answer, but here is an alternative; not any better, just different. Seeing as it's well known that for any cardinal $\kappa$ there are triangle-free graphs of chromatic number $\kappa$ (and order $\kappa$ if $\kappa$ is infinite) it will suffice to prove the following:
Lemma. Given a graph $H$ of order $\kappa\ge2$ we can construct a vertex-transitive graph $G$ of order $\max\{\kappa,\aleph_0\}$ which has the same chromatic number and clique number (also girth, circumference, etc.) as $H$.
Proof. Let $T$ be a $\kappa$-regular tree (meaning that every vertex has degree $\kappa$, no leaves). Partition $V(T)$ into two independent sets $A$ and $W$ (corresponding to a proper vertex $2$-coloring of $T$) and fix an edge-coloring $\varphi:E(T)\to V(H)$ such that, for each $x\in V(T)$, the restriction of $\varphi$ to the set of edges incident with $x$ is a bijection from that set to $V(H)$. Let $G$ be the graph with vertex set $V(G)=W$ and edge set $$E(G)=\bigcup_{a\in A}\{\{u,v\}\in\binom{N(a)}2:\{\varphi(\{a,u\}),\varphi(\{a,v\})\}\in E(H)\}.$$
The graph $G$ is plainly vertex-transitive, since the edge-colored tree $(T,\varphi)$ is vertex-transitive. For each $a\in A$ the induced subgraph $H_a=G[N(a)]$ is isomorphic to $H$; the graph $G$ is the union of the subgraphs $H_a$ ($a\in A$), and the collection of those subgraphs can be well-ordered so that each one except the first has just one vertex in common with the union of its predecessors. From that it's clear that $G$ has the same chromatic number and clique number as $H$, and in fact every $2$-connected subgraph of $G$ is isomorphic to a subgraph of $H$.