Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

What are some ways to prove limits to chromatic numbers, or what are some facts that I could when dealing with large chromatic numbers, such as in the question:

Let G be a graph whose odd cycles are pairwise intersecting, meaning that every two odd cycles in G have a common vertex. Prove that $\chi(G) \leq 5$

Where $\chi(G)$ is G's chromatic number.

I know that odd cycles have chromatic number 3, so any graph containing an odd cycle must have $\chi(G) \geq 3$. I also know that a clique $\kappa_k$ has chromatic number k, but that if $k \gt 3$, then there are at least 2 odd cycles that don't share a vertex.

Are there any other facts about chromatic number that could help me prove this limit?

share|cite|improve this question
The only way to answer your question fully is to first figure out a proof, and then tell you which bounds we used. So, is your actual question, "Can you prove this statement:", or is it, "What are some bounds on the chromatic number?" – Graphth Oct 1 '12 at 18:42

I'm going to assume that your real question is: "What are some bounds on the chromatic number?" By answering this question, I will give you some tools that you can use. I can't tell you if they will be helpful in your proof or not.

Section 8.3 of Graphs & Digraphs, fifth edition, by Chartrand, et al. is entitled "Bounds for the Chromatic Number". And, surrounding sections have other bounds.

For any graph $G$, $1 \leq \chi(G) \leq n$.

If $H$ is a subgraph of a graph $G$, then $\chi(H) \leq \chi(G)$.

For every graph $G$, $\chi(G) \geq \omega(G)$.

If $G$ is a graph of order $n$, then $$\frac{n}{\alpha(G)} \leq \chi(G) \leq n - \alpha(G) + 1.$$

For every graph $G$ of order $n$, $$\chi(G) \leq \left\lfloor \frac{n + \omega(G)}{2} \right\rfloor$$

For every graph $G$, $$\chi(G) \leq 1 + \Delta(G).$$

For every connected graph $G$ that is not an odd cycle or a complete graph, $$\chi(G) \leq \Delta(G).$$

For every graph $G$, $$\chi(G) \leq 1 + \max\{\delta(H)\}$$ where the maximum is taken over all subgraphs $H$ of $G$.

If $G$ is a graph of order $n$ and size $m$, then $$\chi(G) \geq \frac{n^2}{n^2 - 2m}.$$

For every graph $G$ of order $n$, $$\chi(G) \leq \frac{\omega(G) + n + 1 - \alpha(G)}{2}.$$

If $G$ is a graph of order $n$, then

  1. $2\sqrt{n} \leq \chi(G) + \chi(\bar{G}) \leq n + 1$
  2. $n \leq \chi(G) \cdot \chi(\bar{G}) \leq \left(\frac{n+1}{2} \right)^2$
share|cite|improve this answer
How to prove that $\chi(G) \ge \frac{n^2}{n^2-2m}$ thing? – Sayan Apr 13 '15 at 18:45
up vote 1 down vote accepted

The actual proof can be done by removing one of the odd cycles of G and looking at the induced subgraph. Since every other odd cycle had a vertex in common with it, there are no more odd cycles, and the subgraph is bipartite with $\chi(G') \leq 2$.

The odd cycle you removed has chromatic number 3.

The combined graph G must have $\chi(G) \leq 2 + 3 = 5$

This uses some of the bounds given in @Graphth 's answer.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.