## A brief introduction to graph coloring

I hope you go into academia because that was one of the clearest lectures I've ever read. Interesting subject matter too!<P>So how many colors does it take to color in a RISK board?<P>JB<P>------------------
<A HREF="http://pwwoi.keenspace.com" TARGET=_blank>http://pwwoi.keenspace.com</A>

Daxhack
Regular Poster

Posts: 246
Joined: Fri Jan 01, 1999 4:00 pm
Location: Tucson, AZ, USA

Dana !
Do you know the edge coloring algorithms ? I'm researching about it ! Could u help me ? Please contact me as soon as possible ! Thank u so much !
<BLOCKQUOTE><font size="1" face="Verdana, Arial">quote:</font><HR>Originally posted by Dana:
<B>Here's an introduction to graph coloring for non-mathematicians.<P>So a graph is a set of points, called vertices, and lines (called edges) between them. Each edge connects exactly two vertices. (See <A HREF="http://hwg.keenspace.com/d/20010722.html" TARGET=_blank>this comic</A> for an example of a graph.) Now, the vertices usually represent some set of real-world objects, and the edges represent some relationship those objects have. For example, you might make a graph where the vertices are people and the edges connect two people who have gone out on a date. In that case, if we assume there were no same-sex dates, you could divide the vertices into two sets, males and females, and all the edges would go from one set to the other. You wouldn't have any edges completely inside one of the sets. We could think of assigning the color red to the males, and blue to the females. This colors the vertices of our dating graph so that no edge connects two vertices of the same color.<P>When we talk about coloring a graph, this is what is meant: you find a way to assign colors to the vertices so that no edge connects two same-colored vertices. (To be honest, this is the simplest case of graph coloring. There are about a billion variations on this theme.) If a graph can be colored in two colors, then it is called bipartite (because the colors split the graph into two parts). There are graphs which cannot be colored in two colors. The one in the comic is an example. It can, however, be colored in three colors. Can you color it in three? Although three is the minimum needed to color the graph, you could also color it in four, or five, or any larger number of colors. For any number, there is some graph which cannot be colored in that many colors. So you can't possibly hope to color all graphs with a finite, fixed box of crayons.<P>Let's consider another example. Suppose the vertices of our graph represent countries, and there are edges between them whenever those countries share a border (The border must have positive length; bordering at a single point doesn't count). Now, we mathematicians know that no matter how the earth is divided into countries, it can be represented on a flat map so that the border-relationship is preserved. That means our border graph can be drawn on a flat surface ("in the plane") so that no edges cross. (Edges are allowed to touch at their endpoint vertices.) Is there a way to form countries so that our border graph requires 3 colors to color it? 4? 10? 20 colors? It turns out that you can always color it in 4. That's the most publicized theorem in graph theory: The Four Color Theorem. It says that any graph drawn in the plane so that no edges cross can be colored in 4 colors (or less). Alternatively, that means that if there is a graph which requires 5 or more colors to color it, it cannot be drawn in the plane so that the edges don't cross. Such graphs do not represent actual configurations of countries on the earth. It took a few hundred years to finally solve the Four Color Theorem, and even now there are very few people who truly understand the entire proof. By the way, if we wanted to color the states so that no two bordering states get the same color, it does require all four colors. This is not because of "four corners" out in the west, but rather because of things near Virginia and Kentucky.<P>Now, I said there were variations on this coloring theme. For example, some people might want to color the edges of a graph (instead of the vertices) so that no edges with a common endpoint have the same color. This might be useful if your vertices represent parents and teachers, and the edges represent which two people need to have a conference. The coloring of the edges could be used to schedule the meetings so that no meeting times conflict. Another variation is that some folks prefer to colour graphs. Keep the alternate spelling in mind if you decide to look up graph coloring.<P>Of course, graph theorists don't usually care if their work has a direct application to scheduling or map-making. But why mathematicians do what they do is a topic for another day. <IMG SRC="http://www.keenspace.com/forums/smile.gif"><P>---Dana<P>[This message has been edited by Dana (edited 07-23-2001).]</B><HR></BLOCKQUOTE><P>
Viet Nguyen
Newbie

Posts: 1
Joined: Fri Jan 01, 1999 4:00 pm