# Five-coloring plane graphs

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!

-

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.

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

But this is not always true if the vertices of the cycle are connected to other vertices outside the cycle for example:

This would eventually violate the outer-planar property if you add enough edges.

Then the coloring of x,y can be extended to a proper coloring of G by choosing colors from the lists. In particular $\chi(G)$ (indexed l) $\leq 5$"

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.

-
If you could give me an explanation about the proof it would be great because there are really some things that I don't understand enough. – Student Apr 7 '14 at 9:29
It's a long proof. Do you want a high level overview or are there specific parts you don't get? It's a long proof, so if you can better clarify as to your confusion, I can better help clarify. – ml0105 Apr 7 '14 at 12:25
Well I think it's better to just clarify some thinks that I don't understand. -First of all I want to get shure if I understand the logic behind this. -What we do is we take the cardinality of the lists for the vertices of B and for the vertices in the interior bigger than 5 just to prove later(by the two cases) that me can color the planar graphs by only using lists with cardinality 5. Am I right? P.S. Thank a lot for your help. I really appreciate it! – Student Apr 7 '14 at 18:47
I've edited my post. Sorry for the delay. – ml0105 Apr 8 '14 at 15:00
Oh don't worry about that. Just a final question. Can you tell me more about what is the point of precoloring the vertices ? – Student Apr 12 '14 at 18:38