MA 323A Combinatorial Geometry!
Notes on Graph Colorings
Definition: Let G be a graph. Then
Definition: A graph is k-vertex colorable if we can properly color the vertices of the graph using only k different colors.
Similarly, we define k-edge colorable and k-face colorable.
Definition: The chromatic number of a graph G is the fewest number of colors we can use to properly color the vertices of G. This number is denoted X(G). (Actually, that's not supposed to be an X, it's supposed to be the Greek letter chi, but I don't know how to get HTML to produce that character. Sorry!) More formally, we can define
Example: What is the chromatic number of the octahedron, O?
What follows is a listing of Theorems about graph colorings. Some will be proven in class.
The Four Color Theorem: Every planar graph is 4-vertex colorable.
The Four Color Theorem (FCT) has a great history - it remained an open conjecture for a hundred years until Appel, Hacken, and Koch proved it was true by reducing it to almost 2000 subcases and writing a computer program to check all these cases. Thus, while this Theorem is considered to be proven, people still search for a shorter proof. It's also just, plain amazing that such a simple-to-state Theorem would be so incredibly difficult to prove.
The FCT can be re-stated in many different ways. The following versions of the FCT pertain to some of the colorings we've already explored in class:
Theorem: The following three statements are equivalent:
Also note: The first two are equivalent because we can just take the dual of the planar graph and turn vertex colorings into face colorings, and vice-versa. The third one is harder to show -- we proved it in class.
In other words, the 3-edge colorings that we've been making of the dodecahedron and Buckyballs and various things using Sonobe units are equivalent, in a sense, to 4-vertex colorings of general planar graphs. Weird! Also, this allows us to appreciate how difficult 3-edge coloring cubic planar graphs can be, since 4 coloring planar graphs can be very difficult.
Not surprisingly, it is much easier to characterize when a graph is 2-vertex colorable. The following Theorem does just this.
The Two Color Theorem: A graph is 2-vertex colorable if and only if the graph has no odd cycles.
Another way to state that is this: A graph is 2-vertex colorable if and only if it is bipartite. This is very easy to prove, and we'll probably do it in class.
Of course, there is also a Three Color Theorem, but it's a little bit harder to state. To see where it comes from, look at a class of graphs called wheels. A wheel is a graph that consists of a cycle and one vertex in the "middle" which is connected to all the vertices on the cycle. (See the picture below.) An odd wheel is a wheel whose outer cycle is of odd length, and an even wheel has an even cycle for the "rim."
The Three Color Theorem: A planar graph that has all triangle faces is 3-vertex colorable if and only if every vertex has even degree.
One direction of the proof of this Theorem is easy. (Which one?) The other direction can be done in a really cool way by induction on the number of vertices. Oooo!
Here's another good one, which is also REALLY hard to prove!
Grötzsch's Theorem: Every planar graph with no 3-cycles is 3-vertex colorable. (That is, triangle-free planar graphs are 3-vertex colorable!)
There are many, many more coloring Theorems. A whole course could be taught on graph colorings! But for now realize what we've learned about some of the graphs we've been examining: Every cubic planar graph (that is 2-edge connected) is 3-edge colorable. That is, we know that all those Buckyballs that we've been making from PHiZZ units can be properly 3-edge colored. The question is HOW? Just because we know we can do it doesn't mean that it's easy!
Exercise: What do these coloring Theorems say about how many colors we'll need if we use Sonobe units to make "versions" of polyhedra? Will 3 colors always be enough?
Return to Combinatorial Geometry Page