0
$\begingroup$

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?

  • 0
    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?"2012-10-01

2 Answers 2

2

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.

3

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$
  • 0
    How to prove that $\chi(G) \ge \frac{n^2}{n^2-2m}$ thing?2015-04-13