Bounds for X(G)

# 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$. |