Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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:enter image description here

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!

share|improve this question

1 Answer 1

up vote 0 down vote accepted

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.

share|improve this answer
    
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 at 9:29
1  
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 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 at 18:47
    
I've edited my post. Sorry for the delay. –  ml0105 Apr 8 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 at 18:38

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.