(For this problem, I am talking about undirected graphs)

A 4-chromatic graph is graph which requires at least 4 colors for a proper coloring. A proper coloring involves coloring all the vertices so that any pair of adjacent vertices are of different colors. (Note: Adjacent vertices are vertices that have an edge connecting the two together)

A triangle-free graph is a graph in which there are no cliques of size 3 (a group of 3 vertices in which they are all adjacent to each other).

I am approaching by proof by contradiction, but I have to say I have little to show.

  • $\begingroup$ Hi. Can you show a bit of your work on this so far? Or at least some definitions: this way it is easier to help you! $\endgroup$ – MattAllegro May 12 '14 at 19:44
  • $\begingroup$ Much better! I do not know graph theory at all but this will help other users in answering your question properly. $\endgroup$ – MattAllegro May 12 '14 at 20:20

The following is probably not the slickest way, but here it is anyway. Note that there are some details I'm leaving for you to fill in. Of course whenever I say "coloring," I always mean a proper coloring.

For a graph $G$, let $\Delta(G)$ denote the maximum degree amongst all the vertices in $G$. Recall the following famous result.

Brook's Theorem: Let $G$ be a connected graph. If $G$ is either a cycle of odd length or a complete graph, then $\chi(G)=\Delta(G)+1$. Otherwise, $\chi(G)\leq \Delta(G)$.

Next, convince yourself of the following.

Lemma: If $H$ is a triangle-free graph on $5$ or fewer vertices, then either $H$ is a cycle of length $5$ or $\chi(H)\leq 2$.

So now suppose you are given a triangle-free graph $G$ on $10$ or fewer vertices. We may as well assume that $G$ is connected and has at least $6$ vertices. Furthermore, we can assume that $\Delta(G)\geq 4$.

Let $v$ be a vertex of degree $\Delta(G)$, let $A$ be the neighbours of $v$. Note that $A$ is an independent set (i.e, no edges exist between vertices in $A$). Let $B$ be the subgraph induced by the non-neighbours of $v$.

If $\Delta(G)>4$, then $B$ has at most $4$ vertices. By the lemma, the vertices of $B$ can then be colored using two colors, say red and blue. Next, we can color all vertices of $A$ green. Finally, since $v$ is not adjacent to any vertex in $B$, we can color it red. Thus we've found a $3$-coloring of $G$.

If $\Delta(G)=4$, and $B$ is not a cycle of length $5$, then proceed as in the previous paragraph to obtain a $3$-coloring of $G$. So we may now assume that $\Delta(G)=4$ and that $B$ is a cycle of length $5$. Note that this means $G$ has $10$ vertices. In particular, we now know that any triangle-free graph on at most $9$ vertices is $3$-colorable.

Now, if any vertex $w$ in $G$ has $\deg(w)\leq 2$, delete it. The resulting graph $G-w$ has $9$ vertices and so we can color it with three colors. But since the deleted vertex has at most two neighbours in $G$, this means that such a coloring of $G-w$ can be extended to a coloring of $G$ using three colors, and we're done. So now assume all vertices in $G$ have degree at least $3$. Since $G$ is triangle-free, this means that every vertex in $A$ has exactly two neighbours in $B$. So at this point, $G$ looks like:

enter image description here

Suppose a vertex in $b\in B$ is adjacent to all four neighbours in $A$. Since there are no vertices of degree $2$, the two neighbours of $b$ are also adjacent to a vertex in $A$. But then $G$ would not be triangle-free, so no vertex in $B$ can be adjacent to all four vertices in $A$.

Suppose a vertex $b\in B$ has exactly three neighbours in $A$. This forces the two neighbours of $b$ in $B$ to be adjacent to the fourth vertex in $A$, and the neighbours of $b$ in $A$ to be adjacent to one of the two non-neighbours of $b$ in $B$. In a thousand words, $G$ looks like:

enter image description here

But now we can $3$-color $G$ as so:

enter image description here

Finally, we may suppose no vertex in $B$ has more than two neighbours in $A$. But since there are $8$ edges between $A$ and $B$, this means that exactly three vertices in $B$ have two neighbours in $A$. Hence two of these vertices must be adjacent, and so the graph looks like:

enter image description here

Color the vertices as so:

enter image description here

But since $G$ is triangle-free, this is actually a proper $3$-coloring.


I am not sure if this is a direct enough answer for you but this is related to the Mycielski construction.

In Sur le coloriage des graphs", Colloq. Math. 3: 161–162 Mycielski provided a construction of triangle free graphs having arbitrary chromatic number.

Later V. Chvátal (The minimality of the mycielski graph, Lecture Notes in Mathematics Volume 406, 1974, pp 243-246) showed that such graphs are minimal examples.


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.