1
$\begingroup$

This question already has an answer here:

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.

$\endgroup$

marked as duplicate by Misha Lavrov graph-theory May 20 at 3:50

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks! I think I know what to do. $\endgroup$ – Kai May 19 at 23:14
  • $\begingroup$ I changed the question. $\endgroup$ – Kai May 20 at 3:33
  • $\begingroup$ The same strategy should work; there are now several possible 2-connected graphs instead of one, but they are all either bipartite or subgraphs of $K_4$. $\endgroup$ – Misha Lavrov May 20 at 3:52
0
$\begingroup$

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

$\endgroup$

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