5
$\begingroup$

As the title says, I have a simple finite graph whose every odd cycle is a triangle, and I want to show that $\chi (G)\leq 4$.

My idea was trying to use the fact that a graph is bipartite iff it contains no odd cycles. The general direction was: if we somehow "remove" the triangles, we get a 2-colorable graph, and then maybe somehow we can add them back without adding more that 2 colors needed...?

$\endgroup$

1 Answer 1

2
$\begingroup$

Let $G=(V,E)$ be a finite graph in which every odd cycle is a triangle. We can assume that $G$ is a minimal counterexample, so that every proper subgraph of $G$ is $4$-colorable, and $G$ is a connected simple graph. Choose a root vertex $u.$

Let $V_i=\{v\in V:d(u,v)\equiv i\pmod2\}.$ If both of the induced subgraphs $G|V_1$ and $G|V_2$ are $2$-colorable, we're done; so we can assume that one of them contains an odd cycle, which must be a triangle. That is, $G$ contains a triangle $T$ with $V(T)=\{v_1,v_2,v_3\}$ where $d(u,v_1),\ $$d(u,v_2),$ and $d(u,v_3)$ all have the same parity.

Note that $u\notin V(T),$ and a shortest path from $u$ to $v_i$ contains no edge or vertex of $T$ except $v_i.$ Hence there is a path $P$ from $v_1$ to $v_2$ which contains no edge or vertex of $T$ except $v_1$ and $v_2.$ The path $P$ must have length $\ge2,$ but if $P$ had length $\ge3$ then by adding one or two edges of $T$ to it we would get an odd cycle of length $\ge5,$ so the length of $P$ is exactly $2.$ That is, there is a vertex $w\notin V(T)$ which is adjacent to $v_1$ and $v_2.$

By the same token, there is a vertex $w'\notin V(T)$ which is adjacent to $v_2$ and $v_3.$ But if we had $w\ne w'$ then we would have a $5$-cycle $v_1,w,v_2,w',v_3,v_1$ in $G.$ Therefore $w=w'$ is adjacent to all three vertices in $V(T).$ Let $v_4=w=w';$ then the induced subgraph $Q=G|\{v_1,v_2,v_3,v_4\}$ is a $K_4.$

The spanning subgraph $G'=G-E(Q)$ is $4$-colorable. Note that the vertices $v_1,v_2,v_3,v_4$ lie in four different components of $G';$ for, if $v_i$ and $v_j$ ($i\ne j$) were connected by a path in $G',$ then there would be an odd cycle of length $\ge5$ in $G.$ Therefore, in $4$-coloring $G',$ the colors of those four vertices can be assigned arbitrarily; we give them different colors, so that the coloring of $G'$ will also be a proper coloring of $G.$

This argument shows that a finite graph, in which every odd cycle is a triangle, is $4$-colorable. By the Erdős–De Bruijn theorem, the same goes for infinite graphs.

$\endgroup$
3
  • $\begingroup$ Can you explain what $G|V_1$ means? Does that mean the intersection of the two graphs? $\endgroup$
    – Kai
    May 20, 2019 at 4:47
  • $\begingroup$ @Kai $G|V_1$ is the subgraph of the graph $G=(V,E)$ induced by the vertex set $V_1$. That is, it's the graph whose vertex set is $V_1$ and whose edge set is $\{xy\in E:x,y\in V_1\}$. $\endgroup$
    – bof
    May 20, 2019 at 5:05
  • $\begingroup$ Thank you very much! $\endgroup$
    – Kai
    May 20, 2019 at 17:49

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.