📂Graph Theory

Graph Coloring and Brooks' Theorem

Definition

A function $f : V(G) \to [k]$ for a loop-free graph $G$ is called a $k$-coloring of $G$. $$ u \sim v \implies f(u) \ne f(v) $$ If a graph $G$ has a $k$-coloring, it is also said to be $k$-colorable. If it is $k$-colorable but not $(k-1)$-colorable, then that $k$ is called the Chromatic Number of $G$, denoted as $\chi(G) = k$. A graph whose chromatic number is $k$ is called a $k$-chromatic graph.

---

• A loop refers to an edge that connects a vertex $u$ to itself.
• $[k] = \left\{ 1, \cdots , k \right\}$ represents a set of natural numbers from $1$ to $k$. The notion of natural numbers isn’t significantly important here; as long as there are $k$ different elements, it can abstractly serve as the range for coloring. For example, using $[3] = \left\{ \text{red}, \text{blue}, \text{black} \right\}$ is fine, but there wouldn’t be any fundamental difference from using $\left\{ 1,2,3 \right\}$, thus we use natural numbers.

Explanation

Graph coloring in layman’s terms is the mapping—coloring of adjacent vertices with different colors. Since there can be numerous such functions, naturally, our interest lies in minimal coloring, hence the expression colorable is seldom used.

The problem of determining the chromatic number of a graph has always received attention in combinatorial mathematics, among which the notorious Four Color Theorem was a famous problem for a time. Generally, these problems are of the NP class, still awaiting proofs of innovative algorithms and theorems.

The simplest thinkable coloration for any graph is to color the $n$ vertices with $n$ different colors. Such coloring is termed Greedy Coloring, which is obviously the most naive approach. Depending on the properties of the graph, various theorems like the following are known. Among the first theorems one encounters and the most famous when approaching graph coloring is Brooks’ theorem.

Theorems ¹

• [1]: For Complete Graphs: $K_{n}$ and for null graph $G$ $$ \chi(K_{n}) = n \\ \chi(G) = 1 $$
• [2]: It is equivalent for $G$, not being a null graph, to be a bipartite graph and $\chi(G) = 2$.
• [3]: Let the highest degree of simple graph $G$ be $\Delta (G)$, $$ \chi(G) \le \Delta (G) +1 $$
• [4]: Let the number of edges in $G$ be $m$, $$ \chi(G) \le \sqrt{2m+1/4}+1/2 $$
• [5] Brooks’ Theorem: A simple connected graph $G$, if not a complete graph and if the maximum degree is $\Delta (G) \ge 3$, then $G$ is $\chi(G) \le \Delta (G)$