Knowing every odd circuit in a graph is a triangle, prove $\chi(G) \le 4$

Question

Knowing every odd circuit in a graph is a triangle, prove $\chi(G) \le 4$

My approach: an odd circuit requires 3 colors, and an even circuit requires 2. But then I'm stuck. Can you give me a hint on how to proceed? No complete solution please.

Answer 1

If you're familiar with 2-connected graphs, then you can use the following strategy.

First, whenever $v$ is a cut vertex of $G$, we can divide up $G$ into fragments $G_1, G_2, \dots, G_k$ whose union is $G$, such that they all contain $v$ but are otherwise disjoint. We can color $G_1, G_2, \dots, G_k$ individually, then combine the colorings.

This leaves as a base case graphs which are $2$-connected and don't have a cut vertex. With the condition that all cycles in the graph are triangles, you can narrow down the possibilities and then say how to color all of these.

Actually, I believe that you should be able to prove that $\chi(G) \le 3$ for all such graphs.

Answer 2

Hint:

Any such graph will look like a tree with some vertices blown up into triangles (or alternatively, identify the vertices of each triangle in your graph and show that this is a tree). Prove this, and show that any such graph $G$ has $\chi(G)\le 3$.