Find an example of a regular triangle-free $4$-chromatic graph

Find an example of a regular triangle-free $4$-chromatic graph

I know that for every $k \geq 3$ there exists a triangle-free $k$-chromatic graph.

So if I can find a triangle-free graph $H$ such that $\chi(H)=3$, then I can use the Mycielski construction to obtain a triangle-free graph $G$ such that $\chi(G)=4$. However, the regular part keep getting me stuck. I try some odd cycle, I also tried the Petersen graph but still can't get a regular triangle-free $4$-chromatic graph.

I wonder if anyone can give me a hint, please.

• The chromatic number has to be exactly $4$, right? You have no use for triangle-free regular graphs of degree greater than $4$? – bof Feb 13 '15 at 4:05

Discussed this question with my guide after getting a specific answer by joining two Mycielskian of $C_5$ appropriately (so $22$ vertices). He told me the following technique, which can be generalized to handle such questions.

Construct the Mycielskian of $C_5$ (any triangle free $4$-chromatic graph will do). We have five vertices with degree $3$, five with degree $4$ and one with degree $5$. Make five copies of this. Add a new vertex and join to the corresponding degree $4$ vertex in each of the five copies. Do this for the rest degree $4$ vertices. For degree $3$ vertices take two vertices and join both of them to the corresponding degree $3$ vertex in each of the five copies. Now the final graph is regular, triangle free and $4$-chromatic.

This technique is already published (unable to find the paper).

For this general method, you use the exact same coloring in all five copies ($a_i$,$b_i$,...,$e_i$ for $i = 1$ to $11$) of the Mycielskians (color 1 to 4). Every corresponding degree 4 vertex of each is connected to a new vertex (i.e. $a_1$,$b_1$,...,$e_1$, having same color say 1, is connected to a new vertex whose degree is $5$ which can be assigned a different color than 1). Do this for the rest degree 4 vertices ($a_i$,$b_i$,...,$e_i$ for $i = 2$ to $5$). Every corresponding degree 3 vertex of each is connected to two new vertices (i.e. $a_6$,$b_6$,...,$e_6$, having same color say 1, is connected to two new vertices whose degree is $5$ which can be assigned a different color than 1). Do this for the rest degree 4 vertices ($a_i$,$b_i$,...,$e_i$ for $i = 7$ to $10$).

This results in a regular $\Delta$-free $4$-chromatic graph.

PARTICULAR ANSWER: (not using the general method described above which would result in a graph of order $70$)

The following is a particular answer to this question using Mycielskian resulting in a graph of order $22$. These are two copies of Mycielskian of $C_5$. I have not drawn all edges within each Mycielskian to improve the clarity. The left 5 vertices of Mycielskian were degree 4 vertices hence have only one matching, where as the middle five vertices of Mycielskian were degree 3 vertices hence have two matchings to make them regular. • This gives an example with $55$ vertices, comparable with $KG(8,3)$ or the Hoffmann-Singleton graph. How do you generalize this technique for having triangle-free regular graphs with arbitrary chromatic number? – Jack D'Aurizio Feb 13 '15 at 12:33
• Construct triangle free graph with arbitrary chromatic number (Mycielskian for example). Make $\Delta$ (Max degree) copies of it and add the new vertices with $\Delta$ edges to the corresponding vertex (whose degree $< \Delta$) of each copy. Continue till the graph is $\Delta$ regular. – user67773 Feb 13 '15 at 12:41
• @JackD'Aurizio Regarding this particular question, I got a graph on $22$ vertices, but the general method was more elegant (although bigger $55+2*5+1*5 = 70$ vertices). – user67773 Feb 13 '15 at 12:45
• @JackD'Aurizio Agreed. But I was wondering on how to prove minimality. The Clebsch graph you suggested seems to be the minimal, but was looking for a formal proof. – user67773 Feb 13 '15 at 12:49
• (+1) Ok, it looks working. However, Kneser graphs seem to provide examples with fewer vertices for certain chromatic numbers. For instance, $K(3k-1,k)$ is a triangle-free graph with chromatic number $k+1$ and $\binom{3k-1}{k}$ vertices. – Jack D'Aurizio Feb 13 '15 at 12:56

If you're lazy you can check all the graphs on Wikipedia. The Hoffman–Singleton graph, for example, is strongly regular, has girth 5, and has chromatic number 4.

• girth five implies no triangles, in case anyone was wondering. – Jorge Fernández Hidalgo Feb 13 '15 at 3:55
• (+1) Is that the minimal example of a regular, triangle-free graph with chromatic number four? – Jack D'Aurizio Feb 13 '15 at 9:32
• Ok, I've answered this question above. The minimal example is given by the Clebsch graph. – Jack D'Aurizio Feb 13 '15 at 9:56

Another example is given by Kneser graphs $K(n,k)$ with suitable parameters.

By Lovasz' theorem, the chromatic number of $K(n,k)$ is given by $n-2k+2$.

Moreover, if $n<3k$ we have that $K(n,k)$ is triangle-free, so:

$\color{red}{K(8,3)}$ is a triangle-free, $10$-regular graph on $56$ vertices with chromatic number $\chi=4$.

However, the minimal example of a triangle-free, regular graph with $\chi=4$ is given by another "topological graph", the Clebsch graph, with $16$ vertices and degree $5$.

• Any idea on how to prove minimality in case of the Clebsch graph? – user67773 Feb 13 '15 at 11:13
• thanks for the answer, however, I haven't learnt the Lovasz' theorem yet. Is there a way to construct graphs like this? I need to know how to do it so that I can construct every regular graph. – Diane Vanderwaif Feb 13 '15 at 11:31
• @DianeVanderwaif: Lovasz' theorem is $\chi(K(n,k))=n-2k+2$. Do you know how Kneser graphs are built? If not, have a look at their Wikipedia page. They have many interesting properties. – Jack D'Aurizio Feb 13 '15 at 12:29