# 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 $\chi (G) \geq \frac{v}{(v-d)}$

where $\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 $\chi (G) \geq \frac{v}{(v-d)}$

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

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

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

now label the colors with $1, 2, \cdots , \chi(G),$ and for any $1 \leq k \leq \chi(G)$ let $A_k$ be the set of all vertices in $V$ colored $k.$ then clearly $\bigcup_{k=1}^{\chi(G)} A_k=V$ and for any $i \neq j: \ A_i \cap A_j = \emptyset.$ also by the above
remark $|A_k| \leq v-d,$ for all $1 \leq k \leq \chi(G).$ therefore: $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 $G$ be any simple graph, $V$ the set of vertices of $G,$ and $W$ the largest subset of $V$ with this property that no two vertices in $W$ are adjacent. then: $\chi(G) \geq \frac{|V|}{|W|}.$