Coloring

We use $\Delta (G)$ from Definition (Maximum Degree of a Graph).

Definition (Coloring)

A vertex coloring of a graph $G$ is an assignment of a color to each vertex of $G$ so that no two adjacent vertices have the same color. This is an $n-$coloring if only $n$ different colors are used.

Definition (Chromatic Number)

The chromatic number $\chi (G)$ of a graph $G$ is the smallest number $n$ so that $G$ has a graph coloring.

Lemma (Low Chromatic Numbers)

• $\chi (G)=1⟺|E(G)|=0$
• $\chi (G)\le 2⟺G$ is bipartite.
• Determining $\chi (G)$ for more complicated graphs is difficult. For $2-$colorings, once you color a vertex, the is only one possible choice for its neighbors. For $3-$colorings, there are two.

Lemma (Bipartite Chromatic Number)

Obviously, for any Bipartite Graph, the chromatic number is $2$ (by definition!).

Lemma (Path Chromatic Number)

For any Path $P_n,\chi (P_n)=2$, since we can simply alternate.

Lemma (Cycle Chromatic Number)

For any Cycle $C_n,\chi (C_n)=2$ if $n$ is even, but $3$ if $n$ is odd.

Lemma (Complete Chromatic Number)

For Complete Graph $K_n,\chi (K_n)=n$, since every vertex is connected to each other and thus must be different colors.

Lemma (Chromatic Upper Bound)

For $G$ a graph on $n$ vertices, then $\chi (G)\le n$.

Proof: Give each vertex a different color.

The lower bound is given by corollary.

Greedy Coloring

We can try a greedy coloring strategy by coloring vertices one at a time and filling in the ones that do not conflict. If $v$ has $\mathrm{deg}(v)$ neighbors, then it is enough to have $\mathrm{deg}(v)+1$ colors to choose from.

Lemma (Chromatic Upper Bound by Big Delta)

For any graph $G$,

$$\chi (G)\le \Delta (G)+1$$

Proof: Use Greedy Coloring.

This bound is far often from tight. For example, $\chi (K_{n,n})=2$ but $\Delta (K_{n,n})=n$. Note the same message in corollary.

Equality Special Cases

We have two cases where equality is achieved:

1. For $C_n$ with odd $n$, $\chi (C_n)=3$ and $\Delta (G)=2$.
2. $K_n$ for $n>1$, then $\chi (G)=n$ and $\Delta (G)=n-1$.

Brook’s Theorem

If $G$ is a finite connected graph that is neither an odd cycle nor a complete graph, then

$$\chi (G)\le \Delta (G)$$

Proof:

Let $G=(V,E)$. For the special cases, see Equality Special Cases. For $\Delta (G)\le 2$, see Lemma (Big Delta Less Than 3).

Suppose $G$ is not regular. Then there is some vertex $v\in V$ where $\mathrm{deg}(v)<\Delta (G)$. If we can color $G-\{v\}$, then we can try to greedily color $v$. But then

$$\forall w\in N(v)\subseteq V(G-\{v\}),{\mathrm{deg}}_{G-\{v\}}(w)={\mathrm{deg}}_G(w)-1$$

guaranteeing there is at least one color. We can then repeat this for every vertex.

Suppose $G$ is $k-$regular. We want to find vertex $v$ where $u,w\in N(v)$ have the same color.

$"\\usepackage{tikz-cd}\n\\begin{document}\n$

source code

If $G$ is a complete graph, refer to Equality Special Cases. So, since $G$ is not complete, $u,v$ are not adjacent. We can try to color $G-\{v\}$ with $u,w$ as the same color.

If $\{u,w\}$ is not a cutset, then we can recursively color the rest of the graph. If $\{u,w\}$ is a cutset, then split $G$ into two parts. We color each half inductively and change colors so that $u,w$ match[^1].

$"\\usepackage{tikz-cd}\n\\begin{document}\n$

source code

[1]:Let $H_1,H_2$ denote the halves split by $u,w$. You can imagine this is a graph contracted version of $G$.

We have two cases:

Case 1: If $v$ is a cut vertex, we can inductively color each connected component of $G-\{v\}$. We need arrange it so then two (non-adjacent) neighbors of $v$ are the same color. This gives the coloring for $v$.

Case 2: If we have $2$ cut vertices, then $\{u,w\}$ is our cutset. Let $H_1^{\prime }=H_1\cup \{u,w\}$ and $H_2^{\prime }=H_2\cup \{u,w\}$ be our two halves. We inductively find a $k-$coloring $c_1,c_2$ for $H_1^{\prime },H_2^{\prime }$ respectively. However, we need to show that we can make $u,w$ match colors before combining two halves, which gives our coloring.

Case 2A: Suppose we colored $H_1^{\prime }$ such that $c_1(u)\ne c_1(w)$ by greedily coloring keeping $u,w$ be last. If

$$({\mathrm{deg}}_{H_1}(u)<k-1)\vee ({\mathrm{deg}}_{H_1}(u)<k-1)$$

then we can ensure that there is at least one color to ensure the colors are different.

Case 2B. Here, $c_1(u)=c_1(w)$, implying that

$${\mathrm{deg}}_{H_1}(u)=k-1\wedge {\mathrm{deg}}_{H_1}(w)=k-1$$

But since $G$ is $k-$regular, then

$$\begin{array}{rl}{\mathrm{deg}}_G(u)& ={\mathrm{deg}}_{H_1}(u)+{\mathrm{deg}}_{H_2}(u)\\ k& =k-1+{\mathrm{deg}}_{H_2}(u)\\ 1& ={\mathrm{deg}}_{H_2}(u)\end{array}$$

and likewise for $w$. But then this means we can easily find a $k-$coloring $c_2$ for $H_2^{\prime }$ where $c_2(u)=c_2(w)$. Then permute colors to ensure $c_1(u)=c_2(u)$ and $c_1(w)=c_2(w)$, allowing us to combine the halves, and giving us our coloring.

Theorem (Weak Planar Coloring Bound)

If $G$ is a Planar Graph, then $\chi (G)\le 6$.

Proof:

By Theorem (Planar Graphs have Bounded Minimum) we know $G$ has $\delta (G)\le 5$. We apply greedy coloring but on low degree vertices last and proceed with induction on $|V|$. So, if $|V|=1$, then we are done.

Inductively, assume that if we have any planar graph on $n$ vertices, then $\chi (G)\le 6$, then we want to show the same for $G$ with $n+1$ vertices.

Pick $v\in G$ where $\mathrm{deg}(v)\le 5$, which will be the last vertex to color. In particular, we color $G-v$ then color $v$. Since $G$ is planar, $G-v$ is planar, and by the IH, we can color $G-v$. As $v$ has $\le 5$ neighbors, then we must have some available color. Using that, we have a $6-$coloring of $G$.

Theorem (Strong Planar Coloring Bound)

If $G$ is a Planar Graph, then $\chi (G)\le 5$.

Proof: We induct on $|V|$. If $|V|\le 5$, we are done (assign each vertex a unique color). Assume all planar graphs with $k$ vertices have a $5-$coloring, and we want to show this for a graph $G$ with $k+1$ vertices. Pick $v\in V$ where $\mathrm{deg}(v)\le 5$. Again, the goal is color $G-v$ (which we can by the IH), and then add back $v$ and color it.

Case 1: If $\mathrm{deg}(v)<5$, then we have at least one color left for $v$, allowing us to color it.

Case 2: Suppose $\mathrm{deg}(v)=5$. In this case, we cannot greedily color. We get two sub-cases:

Case 2A: If $v$‘s neighbors all use $4$ distinct colors, then at least one color is free. Select that and we are done.

Case 2B: Suppose all of $v$‘s neighbors all have distinct colors.

$"\\usepackage{tikz-cd}\n\\begin{document}\n$

source code

The goal is to recolor one of $v$‘s neighbors to free up a color for $v$.

Attempt 1: Suppose we tried to free up $\text{red}$ on $v_1$ by changing it to $\text{green}$. We can only do this if $v_1$ has no $\text{green}$ neighbors. But then to swap $w\in N(v_1)$ to $\text{red}$, none of $N(w)$ can be $\text{red}$. We can abstract this by finding the Kempe Chain $K_{\text{red},\text{green}}$. It is the connected component containing $v_1$ that includes only $\text{red}$ and $\text{green}$ vertices. We get two cases:

Case 2B.1.1: If $v_3\notin K_{\text{red},\text{green}}$ then can safely swap all the colors from $\text{red}$ to $\text{green}$ and $\text{green}$ to $\text{red}$. This means $v_1$ is $\text{green}$, and we can color $v$ $\text{red}$.

Case 2B.1.2: If $v_3\in K_{\text{red},\text{green}}$,

$"\\usepackage{tikz-cd}\n\\begin{document}\n$

source code

then we cannot swap to free up a color for $v$.

Attempt 2: Suppose we tried to swap $\text{blue}$ and $\text{orange}$ for $v_2$ and $v_5$ respectively. We find Kempe Chain $K_{\text{blue},\text{orange}}$. This means that

Case 2B.2.1: If $v_4\notin K_{\text{blue},\text{orange}}$, then we can safely swap, and we are done.

Case 2B.2.2: Otherwise, we have

$"\\usepackage{tikz-cd}\n\\begin{document}\n$

source code

But then this means that Case 2B.1.2 and Case 2B.2.2 happened at the same time. In particular, both chains must be vertex disjoint since they use different colors, and since $K_{\text{red},\text{green}}$ surround $v_2$, the existence of $K_{\text{blue},\text{orange}}$ means that they must intersect.

But this is a contradiction as $G$ must be planar. Therefore only a single case $2$ for both attempts must be true. The inductive step holds, and we are done.

This is also known as the Five Color Theorem.

Corollary (Four Color Theorem)

Actually, for planar $G$, $\chi (G)\le 4$.