5
$\begingroup$

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.

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

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).


ADDENDUM:

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.

enter image description here

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Jack D'Aurizio Feb 13 '15 at 12:33
  • $\begingroup$ 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. $\endgroup$ – user67773 Feb 13 '15 at 12:41
  • $\begingroup$ @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). $\endgroup$ – user67773 Feb 13 '15 at 12:45
  • $\begingroup$ @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. $\endgroup$ – user67773 Feb 13 '15 at 12:49
  • $\begingroup$ (+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. $\endgroup$ – Jack D'Aurizio Feb 13 '15 at 12:56
3
$\begingroup$

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.

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

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$.

$\endgroup$
  • $\begingroup$ Any idea on how to prove minimality in case of the Clebsch graph? $\endgroup$ – user67773 Feb 13 '15 at 11:13
  • $\begingroup$ 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. $\endgroup$ – Diane Vanderwaif Feb 13 '15 at 11:31
  • $\begingroup$ @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. $\endgroup$ – Jack D'Aurizio Feb 13 '15 at 12:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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