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?

  • 2
    $\begingroup$ This is question 14.1.8 from Bondy and Murty. $\endgroup$ Commented Apr 24, 2013 at 22:53
  • $\begingroup$ That is correct, but what is your point? $\endgroup$
    – Three
    Commented Apr 24, 2013 at 23:16
  • $\begingroup$ I'm pointing it out to help anyone who might answer the question. $\endgroup$ Commented Apr 24, 2013 at 23:21
  • $\begingroup$ Ah, okay. Thanks. $\endgroup$
    – Three
    Commented Apr 24, 2013 at 23:21
  • 1
    $\begingroup$ 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. $\endgroup$
    – fidbc
    Commented Apr 24, 2013 at 23:24

3 Answers 3


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.


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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .