Coloring Outerplanar Graphs

Today, I will talk about a powerful, yet simple theorem from combinatorics that deals with chromatic numbers of graphs–specifically, outerplanar graphs. If you are unfamiliar with the terms I discuss here, please read my previous post that defines what what I am talking about.

Now, the theorem that I want to prove today is the following:

Theorem: Given an outerplanar graph G, its chromatic number \chi(G) \le 3.

Proof: If a maximal outerplanar graph on a set of vertices yields a chromatic number less than or equal to 3, then surely, an outerplanar graph on that set of vertices yields a chromatic number less than or equal to 3 as well. Therefore, proving that the chromatic number of a maximal outerplanar graph is less than or equal to three is sufficient to prove our theorem.

Let a maximal outerplanar graph G be given. Since G is a triangulation graph of a simple polygon graph, choose one of its triangles, \tau, and properly color its vertices with colors from the set {red, blue, green}. Clearly, the chromatic number of a triangle is 3, so we must use all three of these colors to color \tau. Next, pick a triangle, \rho, that shares an edge with \tau. Since \rho and \tau only have one edge and two vertices in common, the third vertex of \rho can be colored with the left over color. Repeat this process of selecting a colored triangle that shares an edge with an uncolored triangle, and coloring the uncolored triangle with the remaining appropriate color until there are no triangles left to color. Since at each stage, the colored portion of G is guaranteed to be properly colored, and the being-colored triangle of G gets properly colored in a way that does not conflict with G‘s previous colors, it is clear that upon finishing, G is properly colored with three colors.

Finally, it is clear that we can not color a maximal outerplanar graph in fewer than three colors since the chromatic number of a triangle is 3, and since a maximal outerplanar graph is comprised entirely of triangles, the chromatic number must be at least 3.

That’s it! Now we know that the vertices of any outerplanar graph can be properly colored in three or fewer colors. But, in order to have enough control over this proof, we had to imagine maximal outerplanar graphs. There does in fact exist a more elegant proof, which I shall talk about next time, however it is based on the four color theorem—which states that if a graph is planar, its chromatic number is less than or equal to 4. The reason for the hesitancy behind using the four color theorem is that it is surprisingly difficult to prove!

The four color theorem was proven in 1976 by Kenneth Appel and Wolfgang Haken. It was the first major theorem to be proved using a computer. Appel and Haken’s approach started by showing that there is a particular set of 1,936 maps, each of which cannot be part of a smallest-sized counterexample to the four color theorem. Appel and Haken used a special-purpose computer program to confirm that each of these maps had this property. Additionally, any map (regardless of whether it is a counterexample or not) must have a portion that looks like one of these 1,936 maps. Showing this required hundreds of pages of hand analysis. Appel and Haken concluded that no smallest counterexamples existed because any must contain, yet not contain, one of these 1,936 maps. This contradiction means there are no counterexamples at all and that the theorem is therefore true. Initially, their proof was not accepted by all mathematicians because the computer-assisted proof was infeasible for a human to check by hand (Swart 1980). Since then the proof has gained wider acceptance, although doubts remain (Wilson 2002, 216–222).

To dispel remaining doubt about the Appel–Haken proof, a simpler proof using the same ideas and still relying on computers was published in 1997 by Robertson, Sanders, Seymour, and Thomas. Additionally in 2005, the theorem was proven by Georges Gonthier with general purpose theorem proving software. [1]

[1] http://en.wikipedia.org/wiki/Four_color_theorem

Advertisements

One thought on “Coloring Outerplanar Graphs

  1. Pingback: The Power of the Four Color Theorem | petemcneely

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