Bounds for X(G)

We are now going to look at some possible bounds for determining the chromatic number of a graph. For very large graphs, determining the chromatic number is often very difficult. These upper and lower bounds are often very important in determining $\chi$ for a graph $G$, since we can reduce the size of the range of values of $\chi$ between integer values $c$ and $d$, i.e., $c ≤ X(G) ≤ d$. If we get that $c = d$, then we can deduce that $\chi (G) = c = d$.

We note that we will restrict $G$ to being a simple graph.

Upper / Lower Bounds for X(G)

#	Upper Bound	Explanation
1	$\chi (G) ≤ | \: V(G) \: |$	We note that if we have a simple graph $G$ on $n$ vertices, then $G$ is $n$-colourable. That is, we could make every vertex in the graph a different colour.
2	$\chi (G) ≤ | [k] |$, where $[k] = \{ 1, 2, ..., k \}$ denotes a good $k$-colouring of $G$.	We note that if we have a good $k$-colouring of a graph $G$, then the chromatic number must be equal or less than this $k$-colouring. If there does not exist a $(k-1)$-colouring for $G$, then we know that $\chi (G) = k$.
3	$\chi (G) ≤ \Delta (G) + 1$	We know that for any simple graph this must hold. A proof of this theorem can be found here.
4	$\chi (G) ≤ \Delta (G)$ (Brooks' Theorem)	We note that this only works for simple graphs where $G$ is not an odd cycle or a complete graph.
5	$\chi (G) ≤ 4$ (Simple Planar Graphs)	We observed that $\chi (G) ≤ 6$ (6 Colour Theorem For Planar Graphs) and $\chi (G) ≤ 5$ (5 Colour Theorem For Planar Graphs) for simple planar graphs (but in fact $\chi (G) ≤ 4$).

#	Lower Bound	Explanation
1	$\chi (G) \geq$ the number of vertices in the largest complete subgraph of $G$	If a graph $G$ contains a subgraph that is a complete graph itself, then $\chi (G)$ must be greater or equal to this value since for any complete graph $K_n$, $\chi (K_n) = n$.