# Intersecting Odd Cycles, Chromatic Number, and the Subgraph $K_5$

Consider a graph $G$ such that every pair of odd cycles in G intersect.
Then $\chi(G) \le 5$. Furthermore, $\chi(G) = 5$ implies $K_5 \subset G$.

Here is the proof of the first claim:

Let $C\subset G$ be an odd cycle and consider $H := G - V(C)$. H contains no odd cycles since $C$ intersected every odd cycle of $G$. Therefore, by a well-known theorem, $H$ is bipartite and can be colored the two colors $\{1,2\}$. Since an odd cycle can be colored with three colors, we may independently color C with $\{3,4,5\}$. Hence, we have produced a 5-vertex-coloring of $G$, proving $\chi(G)\le 5$.

EDIT: After a discussion with fidbc, we figured the following: In the above proof, we must take $C$ to be the smallest odd cycle. Then $C$ must necessarily be chordless, or else there is a smaller odd cycle (using the chord and one of the "halves" of $C$, one of which must be even since $C$ is odd). Since $C$ is chordless, it follows that it is induced, and then the above proof works.

How does one prove the second claim?

• This is question 14.1.8 from Bondy and Murty. Apr 24, 2013 at 22:53
• That is correct, but what is your point? Apr 24, 2013 at 23:16
• I'm pointing it out to help anyone who might answer the question. Apr 24, 2013 at 23:21
• Ah, okay. Thanks. Apr 24, 2013 at 23:21
• If $C$ is not an induced cycle then you might not be able to colour it with 3 colours, you might need to add that assumption. Apr 24, 2013 at 23:24

The key fact to prove the second claim is that if $$\chi(G)=k$$ and $$c$$ is a $$k-$$coloration of $$G$$, then there is a vertex of each color which is adjacent to vertices of every other colour (given that the Bondy and Murty book was mentioned, this fact is exercise 14.1.3 b of that book). I will call this "Fact 1", the proof is as follows:

Your proof of the first statement gives us a $$5-$$coloration of $$G$$ such that there's only one vertex with color 5, call it $$v$$. Then, there must be a vertex $$u$$ of color 3 and a vertex $$w$$ of color 4 such that $$u$$, $$v$$ and $$w$$ form a triangle. Suppose that this doesn't happen, then for every vertex $$u$$ of color 3 adjacent to $$v$$, you can change the color of its neighbours of color 4 to color 5. This will keep the coloring proper, but will contradict Fact 1. Now that you have a triangle, your proof of statement 1 tells you that there is a proper 5-coloring of G such that there is only one vertex of each of the colors 3, 4 and 5. Call them $$v_3,\ v_4$$ and $$v_5$$, respectively. Now, there must a vertex $$u$$ of color 1 and a vertex $$w$$ of color 2 such that the graph induced by $$\lbrace u,w,v_3,v_4,v_5\rbrace$$ is $$K_5$$. Otherwise, you can again contradict Fact 1 by changing the color of all the neighbours (with color 2) of the vertices of color 1 adjacent to $$v_3,\ v_4$$ and $$v_5$$.

Let me give few ideas that might help, although I do not have a complete proof (yet).

Suppose that $G$ has intersecting odd cycles and that $G$ has no $K_5$ as subgraph. We shall prove that $\chi(G)\leq 4$.

Let us suppose that $G$ contains no triangle. Let $C$ be the smallest odd cycle of $G$ (which has at least five vertices). $G-C$ is bipartite with parts $A$ and $B$. Note that every vertex of $A\cup B$ has at most two neighbors in $C$, because $G$ has no triangles and $C$ is a minimum odd cycle of $G$ (having at least three neighbors in $C$, imply on two neighbors at distance at least four in $C$, since $G$ has no triangles, and thus on a smaller odd cycle). Consequently, one can extend a coloring of $C$ with colors 1,2 and 3, to a coloring of $G$ by coloring the whole set $A$ with color 4 and coloring each vertex of $B$ with a color in the set ${1,2,3}$ that does not appear in its neighborhood in $C$.

The problem is then how to solve the case when $G$ has a triangle $C$? I do not know yet how to extend a 3-coloring of the triangle to a 4-coloring of $G$. Of course, the hypothesis of having intersecting odd cycles and having no $K_5$ as subgraph are important now.

For instance, one can prove that if $G-C$ has parts $A$ and $B$ and $A_i$ (resp. $B_i$) corresponds to the set of vertices in $A$ (resp. $B$) with exactly $i$ neighbors in $C$, for every $i\in\{0,\ldots,3\}$, then $A_3\neq \emptyset$ and $B_3\neq\emptyset$, as otherwise it is possible to find a 4-coloring of $G$ by a similar argument as in the previous case. Supposing that $A_3$ and $B_3$ are both non-empty lead us to deduce that $A_3\cup A_2\cup B_3 \cup B_2$ is an independent set, as otherwise one may find a $K_5$ or two disjoint triangles. Since we do not have two disjoint triangles, $A_3\cup B_1$ and $B_3\cup A_1$ are also independent sets. Moreover, there is no edge $a_1b_1$ such that $a_1\in A_1$, $b_1\in B_1$ and $a_1$ and $b_1$ have the same neighbor in $C$.

Yet, I cannot color $G$. The vertices with no neighbor in $C$ are an issue.