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

Question

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?

Answer 1

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

Answer 2

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.

Answer 3

---

there is a counter example! take 𝐾5 and add even number of vertices on every edge of it. furthermore, if a graph is k-colourable, then it must have a complete graph of order k as its topological minor with even number of new vertices on every edge of it.