# graph theory, chromatic number relation

• May 4th 2009, 04:35 AM
Jason Bourne
graph theory, chromatic number relation
Let G be a simple graph with v vertices and every vertex of degree d. Show that $\displaystyle \chi (G) \geq \frac{v}{(v-d)}$

where$\displaystyle \chi (G)$ is the chromatic number, the least k for which the graph G is k-colourable.
• May 5th 2009, 03:26 AM
NonCommAlg
Quote:

Originally Posted by Jason Bourne
Let G be a simple graph with v vertices and every vertex of degree d. Show that $\displaystyle \chi (G) \geq \frac{v}{(v-d)}$

where$\displaystyle \chi (G)$ is the chromatic number, the least k for which the graph G is k-colourable.

Remark: let $\displaystyle V$ be the set of verices of $\displaystyle G.$ if $\displaystyle A \subseteq V$ has this property that no two vertices in $\displaystyle A$ are adjacent, then $\displaystyle |A| \leq v-d.$ this is because if $\displaystyle |A| \geq v-d+1,$ then $\displaystyle |V-A| \leq d-1$ and so

a vertex in $\displaystyle A$ can be adjacent to at most $\displaystyle d-1$ vertices, which contradicts $\displaystyle d$ regularity of $\displaystyle G.$

now label the colors with $\displaystyle 1, 2, \cdots , \chi(G),$ and for any $\displaystyle 1 \leq k \leq \chi(G)$ let $\displaystyle A_k$ be the set of all vertices in $\displaystyle V$ colored $\displaystyle k.$ then clearly $\displaystyle \bigcup_{k=1}^{\chi(G)} A_k=V$ and for any $\displaystyle i \neq j: \ A_i \cap A_j = \emptyset.$ also by the above
remark $\displaystyle |A_k| \leq v-d,$ for all $\displaystyle 1 \leq k \leq \chi(G).$ therefore: $\displaystyle v=|V|=\sum_{k=1}^{\chi(G)} |A_k| \leq (v-d) \chi(G).$ Q.E.D.
• May 6th 2009, 03:05 AM
NonCommAlg
there's a lower bound for the chromatic number of any simple graph, which generalizes your problem and the proof is just a simple modification of the proof i gave you:

let $\displaystyle G$ be any simple graph, $\displaystyle V$ the set of vertices of $\displaystyle G,$ and $\displaystyle W$ the largest subset of $\displaystyle V$ with this property that no two vertices in $\displaystyle W$ are adjacent. then: $\displaystyle \chi(G) \geq \frac{|V|}{|W|}.$