Graph with no 3-clique that needs at least 4 colors

Question

Give an example of a graph that has the following properties.  (Note that you need to give a single graph as the answer.)

1. The graph does not contain a triangle (that is, a clique of 3 vertices) as a subgraph.
2. Graph needs at least 4 colors for a proper vertex coloring

[If you think that such a graph is not possible, then prove that statement.]

Answer 1

My attempt at making a triangle-free, 4-coloring graph.

Answer 2

This is not possible because any graph that has no circuits with an odd number of vertices has a min vertex coloring of 2.

Comments

Such a graph is possible actually.

---

What would such a graph look like?

---

So, that is the original question.  :-)

If you are looking for a hint: see a pentagon (C5) graph as a starting point.

In general, it is possible to generate a graph with as large chromatic number as you like, and that it still remains triangle (K3) free.

---

Would this be an example?

https://ibb.co/ksDFRo

---

This specific graph is 3-colorable.  I am sure you can reassign the color labels to make it colorable in 3 colors.  I have also posted it on Slack for others to try to solve.

But overall, I think you are starting to draw these kinds of graphs, and that is awesome!

Answer 3

A cycle of length 5 is the smallest odd cycle, and cycles of odd length are known to be triangle-free. I added the vertices accordingly to meet the 4 colors constraint. 

Comments

Seems 3 colorable to me.

---

I started with vertex 1 and gave a blue followed by purple for 2,6,0 since blue is again a chance I gave blue for 3,5 and 7. The vertex 4 and 9 cannot be either purple or blue and have to be different for sure hence having 4 different colors vertices ...am I missing something here?

Answer 4

I started with a pentagon added a node inside it and then just went on from there removing and adding edges while making sure no 3 clique existed. I couldn't find the attach image button so I have a link here https://ibb.co/YNrfXzp with my graph

Answer 5

Below graph does not contain any triangle and it is 4 colorable as shown. This graph is known, it is called "Grötzsch Graph".

Some sources for more information about the graph:

• Wiki 
• Wolfram