Graph Theory 5: Colorable graphs

Last time I showed when Euler paths can exist in a graph. Next I want to start playing around with colors in graphs. The idea is to color the vertices in a graph for varying purposes. The main use is trying to color graphs so that no colors “touch” each other. That is if you use red, blue, and green to color vertices, then none of the red ones connect to another red one and so on.

For example if we have the easy graph:

\setlength{\unitlength}{5cm}  \begin{picture}(0,0)  \put(0,0){\circle*{1}}  \put(.5,.5){\circle*{1}}  \put(1,0){\circle*{1}}  \put(0,0){\line(1,0){1}}  \put(0,0){\line(1,1){.5}}  \put(.5,.5){\line(1,-1){.5}}  \end{picture}

How many colors do we need to make sure that no two vertices of the same color are adjacent? The answer is pretty clearly three. The reasoning is a little hard to see, so we should look at another. How many colors do we need for this graph?

\setlength{\unitlength}{5cm}  \begin{picture}(0,0)  \put(.75,0){\circle*{1}}  \put(0,1){\circle*{1}}  \put(2.25,0){\circle*{1}}  \put(3,1){\circle*{1}}  \put(1.5,2){\circle*{1}}  \put(.75,0){\line(1,0){1.5}}  \put(.75,0){\line(-3,4){.75}}  \put(0,1){\line(3,2){1.5}}  \put(1.5,2){\line(3,-2){1.5}}  \put(2.25,0){\line(3,4){.75}}  \end{picture}

We can start anywhere, say on the bottom left and make it red. Then that means we need to make the ones that it touches NOT red, so how about blue. Then neither of the next two can be blue, but we want to use the minimum amount of colors so we can use red again, but here is where the problem occurs.

Therefore we need a third color to color this graph properly. My goal is to show when a graph only requires two colors, these types of graphs are called 2-colorable graphs or bipartite graphs. The bipartite part comes from being able to put all the vertices into two different sets (based on only needing two colors to separate all the vertices).

The two examples that I’ve shown will lead us in the right direction. There is something that keeps happening and it is based on the number of vertices and the idea of a cycle. Even if I had put in more lines, the same situation would still have happened while going around that cycle. That is to say, putting in MORE lines is not going to make the graph any easier to color.

So if a graph has that triangle (note it doesn’t have to be in the shape of a triangle, just a 3 vertex cycle) then even if there are a lot more vertices and lines in the graph, it will still need at least 3 colors because of those 3 points. The same thing happens if we have a 5-cycle like above, even if it is just within a much larger graph we we still need at least 3 colors because of that portion.

You can see what happens if you draw a 7-cycle. Instead of filling in the colors the way I did it for the 5-cycle, it may be easier to think about starting in one spot and going in one direction, alternating colors. Eventually you get back to the start and find that you need a third color. This happens because there are an odd number of vertices.

Again, I am drawing the graph in these shapes so that it is visually easier to understand what is happening, but remember that the shape of the lines and where the points are do not actually matter. What matters is how they are connected, so even if I moved the vertices and made the edges squiggly, but kept the same things attached in the same way, it would still be the same graph.

From this you can see what the general case should be. Anytime there is an odd cycle, the graph will require more than 2 colors. It turns out that the reverse statement is also true, that is, if the graph requires more than 2 colors, then there is an odd cycle.

These two statements are logically equivalent to saying: A graph is 2-colorable if and only if it contains no odd cycles. (If and only if means that both statements imply each other). Next time I will prove this statement in a more formal way.

Advertisements
This entry was posted in Graph Theory and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s