# How to approach proving things about large chromatic numbers?

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?

-
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$
-
How to prove that $\chi(G) \ge \frac{n^2}{n^2-2m}$ thing? – Sayan Apr 13 '15 at 18:45

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.

-