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?
Best Answer
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.