Triangle free planar graphs are 4-choosable (4-list-coloring)

1.5k Views Asked by At

Thomassen’s theorem states that every finite simple planar graph is 5-choosable.

If a planar graph has no triangle, then how to prove that it is 4-choosable?

Such graph would either have no cycle or have $C_n$ such that $n\geq4$.

If the cycle is odd then three colors are needed for proper coloring.

But still I have no idea to prove that it is 4-choosable ($|L(v)|\geq 4$)

1

There are 1 best solutions below

0
On

We first prove a claim which will help us prove the second claim in the question as the second claim in the question is the main focus of the question and the first claim is seems to be understood:

So let's say that we have been given a graph $G$, we will use the letter $E$ to denote the set of edges of the graph, we will use the letter $F$ to denote the set of faces of the graph, and we will use the letter $V$ to denote the set of vertices of the graph. We will first show that if $G$ is a planar graph without any triangles then it is true that the following inequality is satisfied: $|E|\leq 2|V|-4$.

So here comes the proof: we consider the sum $\sum_{f \in F}len(f)$. here $len(f)$ denote the number of edges bounding the face $f$. The sum is summing the length of the boundary of each faces. We note that each edge of the graph is counted twice for in the summation once for each of the faces that it touches.(There is an issue here, I don't know what happen if the graph is just a single edge, because in that case the lenth of the boundary of that face is 2, but suppose we don't have that situation for now.) So we therefore have the identity $\sum_{f \in F}len(f)=2|E|$. But given that the graph has no triangle, we can assume that $len(f) \geq 4$ for all faces $f$. Namely, the number of edges encircling a face is greater than or equals to $4$. Hence we will have $4|F|\leq \sum_{f \in F}len(f)=2|E|$. We now apply the Euler theorem which says that $|V|-|E|+|F|=2$ to get $4(2+|E|-|V|)\leq2|E| \iff |E|\leq 2|V|-4$. So this show the claim that we have there.

Now we are ready to prove the second claim stated in the question that triangle free planar graph is 4-colorable. We'll prove the claim using induction on the number vertices of the graph. Base case: the graph has one vertex and the claim is true. Inductive step: suppose that the claim is true for any triangle free planar graph with n vertices and now we are given a triangle-free n+1 vertex planar graph $G$.

We now show that $G$ has a vertex of degree at most $3$. We show this because it is going to be helpful in proving the claim. We will prove this claim using contradiction, so suppose that the claim is not true, and so suppose that all of the vertices of the graph $G$ have degree at least $4$, namely, having degree 4 or more. Then when summing all the degrees for each vertex, we expect the following: $4|V(G)| \leq\sum_{v \in V(G)} deg(v)=2|E(G)|$. The equality after the inequality is because of the hand shaking lemma. By the first claim that we showed above, we get $4|V(G)| \leq =2|E(G)| \leq 4|V|-8$ and this gives a contradiction. Namely, we cannot have $|V(G)| \leq |V(G)|$ minus some positive number. And therefore this contradiction proves that our assumption that $G$ didn't have a vertex of degree $3$ or less is false and that $G$ has indeed have a vertex of degree at most $3$.

Now we are ready to continue the proof of the second claim stated in the question. So we can start by finding such a vertex $v$ of degree less than or equals to $3$ in the planar graph $G$ and we removes it from $G$. Then $G-{v}$ is also triangle free and planar and so by inductive hypothesis, the graph $G-v$ is 4-colorable. So we can therefore color $G-{v}$ in 4 colors and then consider coloring the vertex $v$ to get a coloring for the graph $G$. But as vertex $v$ is adjacent to at most $3$ neighbors in $G-v$, there is a color in one of the $4$ color that was used to color the vertices of $G-{v}$ that wasn't used in any of the neighbhors of $v$. We color $v$ using that color which we haven't use and then we get a $4$-coloring of $G$ which is proper. And therefore, this proves the second claim of the question.