These days I've been reading about graph coloring. Right now I'm dealing with the five color theorem. I know how to prove that every planar graph is 6 and 5 colorable. I'm looking on the proof of the theorem:"Every planar graph can be 5-list colored".I've found a book and some pdf materials about this problem.The way they prove it is by using induction when two vertices are precolored but there are some things that I don't understand.
1.It takes the assumptions:
a)The cardinality of C(v)>=3 for all other vertices v of B
b)The cardinality of C(v)>=5 for all vertices v in the interior
I don't really understand why it takes these assumption.
For the first one I guess because in every circle if we have an odd number of vertices it will take us 3 colors to color the cycle and if we have and even number of vertices it will takes us 2 colors. But this is not always true if the vertices of the cycle are connected to other vertices outside the cycle for example:
So in these case we will need 3 or more colors and this is why the cardinality of C(v)>=3.
After these assumptions are taken it says :"Then the coloring of x,y can be extended to a proper coloring of G by choosing colors from the lists. In particular X(G)(indexed l)<=5"
Can anyone help me by giving a better explanation ?
The link to the pdf material: http://math.unco.edu/facstaff/Roberson/Docs/MATH%20695/5%20Color%20Theorem.pdf
There is a mistake in the figure for the case 1 because G1 and G2 are wrong positioned.
Thank you very much!
This is correct. We actually have a theorem dealing with outer planar graphs. Any graph with no interior vertices is at most three-colorable. You can read more about them here: http://en.wikipedia.org/wiki/Outerplanar_graph
This would eventually violate the outer-planar property if you add enough edges.
We can easily a construct a planar graph where $\chi(G) = 5$, so we assume $\chi(G) \geq 5$. We then construct conditions limiting us to at most $5$ colors. Are you looking for a more in-depth explanation of the proof, or just the explanation of the assumptions?
Edit Think about this in terms of colors. I think you're getting confused in terms of cardinalities of sets. So we have a couple cases. The first is that we have a cycle. We require three colors at most to color any cycle. So if we take a chord and connect two vertices of different colors, we are still doing good.
The big part of the proof lies in this next step. It's a contradiction argument. We start by picking a vertex adjacent to five other vertices, and removing it (and all incident edges). This modified graph we will call $G^{\prime}$. This is an extremality argument. That is, we assume an extreme case of planarity. We know this is possible by induction. Let the neighbors of $v$ be $v_{a}, v_{b}, v_{c}, v_{d}, v_{e}$ (labeled as they are colored).
So now here's the trick part. We pick two colors $\{a, b\}$, and we consider a subgraph of $G^{\prime}$ only of vertices colored using $a, b$. We include only edges connecting these two colors. So if two different colored vertices are on the same component, there is a vertex color-alternating path between them. Otherwise, we can reverse the coloring of the vertex of $v_{a}$ as using color $b$, and color $v$ with color $a$.
We apply the same argument with colors $\{c, d\}$. So if we re-color vertex $v$ with color $b$, we're good. Otherwise, we can connect $v_{c}, v_{d}$ with only a $c,d$ vertex-colored path. That would end up intersecting with the $\{a, b\}$ colored subgraph though, a contradiction.
I actually found a really nice (and short) proof of the Five-Color Theorem: http://math.byu.edu/~forcader/FiveColor.pdf
And Wikipedia has a good proof.