colorings of plane graphs
Colorings of plane graphs
This is the first draft of this write-up. Corrections of its contents and suggestions are welcomed.
A planar graph is a graph that can be embedded on a sphere or plane. A plane graph is such a graph together with a choice how to embed it; its faces are the resulting regions of surface separated by edges.
In graph theory however there is usually an extra condition a coloring has to satisfy to be valid. Unless specified otherwise, the condition is that adjacent items must be given distinct colors — two edges meeting at a vertex must have different colors, two faces with a common border must too.
Because of the history of the subject, being couched in terms of coloring maps, faces have often been called “countries” and the plane graph a “map”.
A word on “border” in the context of face coloring. For countries to be considered adjacent it is not enough to just meet at one point. The reason is that that would make coloring problems uninteresting: divide a region into as many countries as you want, arranged like a pie chart, and any number of colors would be required if touching at a point did qualify.
So in a map which has a portion shaped like , both the North and South countries border both the East and West countries, but South does not border North so they’re allowed to have the same color, and West is likewise allowed to have the same color as East. Now consider a small border adjustment from to where we’ve added one extra constraint: now North and South must have different colors. If it was possible to color the old map with a certain number of colors we can’t be certain we can still color the new map. Conversely however, if we can color the new map we can certainly color the old map (using the same color assignment even).
If we are given any bridgeless planar graph (not necessarily trivalent), we can give any vertex with valency 4 this treatment, splitting it into two new vertices of valency 3 and a short new stretch of border, adding a constraint on coloring. Vertices with valency can be given the same treatment in steps, creating vertices of valency 3 and new pieces of border which only makes the problem harder: if we can still color this, we can also color the original.
2-valent vertices are simply funny features along an ongoing border between two countries, and 0-valent vertices funny features within the landscape. Removing them does not alter the coloring exercise. And finally 1-valent vertices create a bridge; we do not want them nor do we want any other bridges, because at such an edge a country meets itself on the other side of the border, making it impossible to have a color change there. This is why face coloring theorems are stated for bridge-free graphs only.
By now we have only vertices left of valency 3 so our new graph is trivalent (cubic). And if it can be -colored (for any ), then so can . This completes the proof of
Lemma 0 Any bridge-free planar graph can be 4-colored any bridge-free planar trivalent graph can be 4-colored.
as the direction was argued above, and the direction is immediate (any includes all the trivalent ones).
Note the lemma does not state either side of the “iff” is true, merely that they are equivalent. The left-hand side is known as the four-color theorem; having the right-hand side equivalent to it gives statements on trivalent graphs a more general importance.
One last point: we will consider the graph drawn on a sphere. Or, what is the same thing: if we draw it on a plane, we will also consider the infinite outside area to be a face. If you were thinking of your graph as a map subdividing a finite continent into countries just call the outside Oceania and color it blue.
This convention too only makes the coloring harder: considering the outside to be a colorless sea allows countries with a shoreline to be of all four colors, while coloring Oceania (say) blue only allows those countries three different colors (just like any other set of countries with a common neighbour). Again, if we can color this, we can color plane maps of any other convention.
A Tait coloring of a trivalent graph is a coloring of its edges with only three colors, such that at each vertex the colors of the three edges there are different. After Peter G. Tait (1831–1901), Scottish physicist (http://www-history.mcs.st-andrews.ac.uk/Mathematicians/Tait.htmlbio at St Andrews), who in 1880 proved the following
Theorem 1 (Tait) A bridge-free trivalent plane graph can be face-colored with 4 colors if and only if it can be edge-colored with 3 colors.
We will not give our four colors such poetic names as red or green, instead they will be given two-bit labels (0,0) and (0,1) and (1,0) and (1,1), formally vectors in , the vector space of dimension 2 over the finite field of order 2.
Edge colors used will be the difference between the face colors on either side of the edge. Because has characteristic 2, differences are the same thing as sums (so it doesn’t matter which we subtract from which). They are carried out (mod 2) on the individual coördinates (in terms of bit patterns: addition without internal carry, that is, the xor operation).
Note that the assignment of labels to face colors is quite arbitrary (e.g. has no special significance) but the assignment to edge colors is less arbitrary: here really means something. It means a border between faces of the same color, exactly the thing that shouldn’t happen. You could say face colors are “position vectors” (where is an arbitrary point) while edge colors are “free vectors”, differences between position vectors.
Proof of : let and be the sets of faces and edges, let be a valid face-4-coloring, and the edge coloring we are trying to construct from . Let be any edge, and and the faces it separates. Now being valid means so . This means really is an edge-3-coloring .
It is also easy to see is a valid coloring: let and be any two edges meeting at vertex p say, and let , and be the three faces found around p such that separates and , and separates and . By being valid we have from which .
Note in passing that the three edge colors around p all being different (and nonzero) means they must be (0,1), (1,0), (1,1) in some order. That means they sum to in a valid edge-3-coloring, a result we will use.
To construct from you might pick a color, give it to the country you’re in, and travel the world. At each border, add its edge color to the previous face color and assign that to the new country. I called edge colors differences rather than sums for that reason: if a journey visits faces , and the face colors everywhere have to be such that the edges crossed have colors , , … then the color reached should be colors of edges crossed.
So we construct by “integrating” (and indeed, “plus a constant”, the arbitrary color of the first country). If we can do that without contradiction between all possible journeys, this “potential” will automatically have as its “gradient” as it should. Remains to prove the “integral” is independent of path taken, in other words that circular paths “integrate” to zero.
Thus far we haven’t used the fact that we’re in a sphere or plane! Of course, the use of “faces” at all means we have an embedding of a graph in some surface; the fact we didn’t use yet is that the surface has genus 0. Indeed, the forward half of Tait’s theorem (valid implies valid ) is true in surfaces of any genus. For the reverse half (valid implies valid ) we need to use the topological properties of the plane or sphere.
There are various ways of doing that. One wonderfully simple proof found in Wilson [Wil02], adapted here to use the notation, relies on the graph being embedded in a plane. For a graph embedded in a sphere that entails choosing a country and puncturing the sphere in the interior of that country; it corresponds to the choice of giving that country the face color (0,0).
Proof of : the subgraph formed by edges of the two colors (1,any) is regular 2-valent. So is the subgraph formed by edges of the two colors (any,1). Such graphs consist of disjoint cycles. In a plane, such cycles have a well-defined interior and exterior. Every face has a number counting the number of (nested) cycles of it is inside, and similarly a number with respect to .
Let and be the residues of and (mod 2). Give the face the color . This is clearly a face-4-coloring. And it is valid: to reach any neighbouring face we cross an edge with color where iff is inside a number of cycles that differs by 1 from , likewise iff is inside a number of cycles that differs by 1 from . So has color and we know and are not both zero.
Tait himself hoped to prove face-4-colorability, via edge-3-colorability, in the following way.
Lemma 2 (Tait) A trivalent plane graph that has a Hamiltonian cycle can be edge-colored with 3 colors.
A Hamiltonian cycle is a closed path that visits every vertex exactly once (and yes, that Hamilton). We dropped the “bridgeless” qualifier because having a cycle in which every vertex is involved means no bridges: for any vertices p and q you can travel between them via the Hamiltonian cycle, and back via all different edges using the other half of the cycle. That would be impossible with a bridge: pick p and q either side of the bridge, now two routes between them would have to use the same edge (that bridge).
Note also that in a trivalent graph the number of edges equals where is the number of vertices. But is an integer, so is even.
Proof of lemma: the Hamiltonian cycle, having vertices, also has edges, which is even. Color them alternatingly red and green. Each vertex now has one red and one green edge; color the third edge blue.
So Tait next tried to prove every planar graph has a Hamiltonian cycle. Unfortunately, some don’t.
A vertex coloring
Curiously, the property that a graph is face-4-colorable, which turned out to be equivalent to being edge-3-colorable by Tait’s theorem, is also equivalent to admitting a certain kind of vertex-2-coloring. This seems to have been discovered independently a few times, most notably by Percy J. Heawood (http://www-history.mcs.st-andrews.ac.uk/Mathematicians/Heawood.htmlbio at St Andrews).
We can call the vertex colors black and white, but think of them as representing values and interpreted as residues (mod 3). This is not the kind of coloring where adjacent items have to be of different color! It does have another more global constraint though: around any face, the vertex colors must sum to 0 (mod 3).
Theorem 3 A bridge-free trivalent plane graph can be edge-colored with 3 colors if and only if it can be vertex-colored in the way just explained.
Rename the three edge colors to 0, 1 and 2 interpreted as residues (mod 3). These are again “position vector”-like; there’s no special significance to being 0. Let be this new relabeled verion of the old .
We construct a vertex coloring from as follows: assign color to a vertex if the edges there have colors 0, 1, 2 going clockwise; if counterclockwise. If the edge coloring is valid, it is possible to define an this way.
Note this makes the vertex colors differences of edge colors in the following sense. If we travel around a face counterclockwise (i.e. always turning left) and and are two successive edges joined at vertex p, then . If instead we turn right to edge say, we get .
Proof of : Based on , define as above. To prove it is valid. Pick any face , and any edge in it, let . Go round the face counterclockwise one whole cycle. Now
(mod 3). Which proves the sum of values around the cycle is zero.
The same argument works in reverse: if is a valid vertex coloring then, in any one cycle, we could assign an arbitrary color to an edge and, going round counterclockwise finding vertices p, q… we could assign to the edges after the colors , , and so on. Because sums to zero around the cycle, it consistently assigns edge colors (e.g. edge again gets color once around the cycle) and because is never zero, we never get the same edge color for successive edges.
But this isn’t yet enough. Given an satisfying its rule, we can start reconstructing by this “integration” process. We just saw it works locally on the level of single face boundary cycles. As with the previous theorem however, the problem with “integrating” is to prove this can be done unambiguously on a global scale, for which the topological properties of genus 0 surfaces must again crop up somehow.
I will choose to use the following property of planes and spheres:
Lemma 4 With a plane graph of faces on a genus 0 surface, it is possible to enlarge a collection of 1 face to faces, one face at a time, in such a way that the area covered remains simply connected throughout.
Simply connected means that the area covered is topologically equivalent to a disk, that it doesn’t enclose any isolated area. Its boundary is a simple closed curve. Imagine the area covered by the collection of faces as shaded. On a sphere, the area covered being simply connected means there is a single connected shaded area inside the boundary and a single connected unshaded area outside, and that the boundary is one closed curve. Of course, while the outside starts off big, it is reduced to just one face by the time the inside has reached faces.
Proof of lemma: start with one face shaded. At each stage, there will be other faces immediately bordering the area shaded thus far. Choose one, call it . If accreting it to the side of the growing shaded area would leave it simply connected, take it and move to the next step.
Now suppose misbehaves, that adding it would enclose (one or more) unshaded region(s) . Of course on a sphere we are already enclosing an unshaded region, the whole outside. So what is really happening if misbehaves is that adding it would split the remaining outside into two (or more) pieces. Choose any one of those pieces and let that be our region .
Note that each of those pieces, including , contain some faces that border the already shaded area. The way it works is this: The boundary of the shaded region has stretches where it borders , and because was chosen as a face that borders the shaded area. If it doesn’t misbehave; if then adding it would split the new outside into regions: in between the stretches where the shaded area borders there are stretches where each time it would border one of those regions.
Choose a face from the faces of that border the shaded region, and try adding it. If that would fail too it would be by splitting the outside in more than one region. Choose one of those that does not contain and call it . Because it does not include , it is wholly contained within one of the regions adding would have created, namely . In fact i.e. it has at least one fewer country than .
Choose a face from the faces of that border the shaded region, if this doesn’t work either choose a that does not contain , and so on.
Now only has finitely many faces, and . So things can go wrong only a finite number of times. We end up with a country that can be added without budding off a piece of outside.
Now we can finish our proof of Theorem 3.
Proof of : Pick one face. We saw we could pick an arbitrary color for one of its edges and then continue assigning colors based on going round, in a valid way. Shade the face to mark it as “done”.
Now pick additional faces along the lines of lemma 4. Keeping the boundary of the shaded area simply connected means that each new face borders the previous shaded area along a single stretch of boundary (say edges going counterclockwise), and this means the portion of the boundary of the new face where the edges ( say) don’t have colors yet is also a single stretch.
This means we can edge-color the additional face validly: give the color it already has, and go round turning left each time assigning edge colors based on . This must agree with the colors for we already assigned consistently, and gives new colors for (which are now also consistent with the rest) and gives the same color again to because is valid.
Once we have covered faces, the last face already has all its edges colored, validly.
It’s a pity there doesn’t seem to be an easy way to find such a vertex coloring from scratch (thereby making the four color theorem much more simple to prove). There cannot be a very obvious way to find one. For example, valid face-4-colorings and edge-3-colorings of the dodecahedron correspond to a vertex-2-coloring that uses 4 of one color and 16 of the other color. It’s hard to see how any automatic scheme could spontaneously break the symmetry and treat 4 of those 20 vertices differently.
The four-color theorem says every bridgeless trivalent plane graph has a valid face-4-coloring. It is equivalent to saying it has a valid edge-3-coloring. And now it is equivalent to saying it has a valid vertex-2-coloring. The next thing would be a valid something-1-coloring, and it shouldn’t be too hard to prove that things can all be colored with 1 color! Unfortunately, we seem to have run out of graph elements to take the place of that “something”.
A corollary: -gon faces
Consider a valid vertex-2-coloring , with some black () and some white () vertices. Around each face, they sum to 0 (mod 3).
Now consider the following modification: pick any vertex, and replace it by a tiny triangular country. If we give the three new vertices the opposite color from the old vertex, the coloring is still valid (in each of the three adjoining faces, one is replaced by two which counts as the same).
Conversely, if the graph had any triangle face we could replace it by a single vertex. The only way three or can add to zero (mod 3) is if they were all of the same sign, so we replace it by one vertex of the opposite sign.
Now suppose we expand all white vertices to black triangles. Or vice versa. We saw each single modification leaves a valid vertex coloring valid. So once we’re done and only have vertices of the same color, the coloring must still be valid. That can only mean one thing: every face now has a number of vertices divisible by 3. Not only the triangles we added, but also the original faces, which must have grown to 6-, 9-, 12- etc. -gons.
Theorem 5 A valid vertex coloring as in Theorem 3 exists if and only if it is possible to modify the plane graph, turning some vertices into triangles, in such a way that we end up with only faces whose size is divisible by 3.
Proof of We just did it.
Proof of We are given such a sequence of modifications where every face ended up as a -gon. It is very easy to give this a valid vertex-2-coloring: just give every vertex the same color. Now undo the modification step by step, each time coloring the new single vertex the opposite color from the triangle it replaced. Modifications and their reversals preserve the validity of vertex-2-colorings, so by the time we have undone every modification the graph is still validly colored.
This gives yet another corollary of the four color theorem: that we can always find such a modication to -gon faces.
The dual of a bridgeless plane graph is formed as follows: place one vertex of inside each face of . For each edge of , separating faces and , draw one edge of from its vertex in to its vertex in , in such a way that the only edge of it crosses is , and so that it crosses at a point other than its endpoints.
This construction creates faces of that each enclose one vertex of and every one of those vertices is thus enclosed, making likewise a dual of .
To prove that assertion: let p be a vertex of , surrounded by faces , and with edges , radiating from it. All those edges will be crossed by edges of forming a closed cycle because they connect the vertices of placed inside , going round. There are no other edges of crossing our edges, and no edges of nearer to p to cross, so the cycle forms the boundary of a face. This shows every vertex of has a dual face of .
To show every face of is now accounted for, we can invoke Euler’s formula. has vertices, edges, faces, with . For we have by construction vertices, edges, and an unknown number of faces. By the previous argument there are at least the faces with vertices of in it. But by (and and and ) must equal that .
Modern formulations of the four color theorem usually take the dual view. In stead of a face-4-coloring, a vertex-4-coloring. Note this is different from the vertex-2-coloring in the previous sections; it has the standard constraint that adjacent vertices must have different colors.
The subject has colorful beginnings. Francis Guthrie was born in England in 1832, obtained firsts in both mathematics and law, taught mathematics in South Africa until his death in 1899 and also found the time to get involved with railroad construction and to make his name in botany. One day he noticed something when coloring a map of the counties of England — the original four-color conjecture. And on 23 October 1852, in London, his brother Frederick asked his own math professor Augustus de Morgan about that observation (“With my brother’s permission”). De Morgan consulted Hamilton (“A student of mine asked me to day to give him a reason for a fact which I did not know was a fact — and do not yet.”). The latter didn’t think much of it and quipped he didn’t have time for that “quaternion of colours”. The problem didn’t go away though, Cayley dug it out again, Kempe gave his flawed proof that stood for 11 years, and the rest is history [FW77, FF94].
The four-color conjecture (now four-color theorem) has loomed large over graph theory. The story how Kenneth Appel, Wolfgang Haken and John Koch found the proof by computer in 1976 is well known. Perhaps it has been fortunate the theorem resisted proof so long, because it has been a motivating force for many exciting developments in graph theory. This includes important results in graph coloring such as Vizing’s theorem, but also work that transcends the bounds of graph theory, such as that by Whitney and Tutte on what is now called matroids.
And the future? Hadwiger’s conjecture can be regarded as a generalisation of the four-color theorem. And it is still open.
Oystein Ore, The Four-Color Problem,
Acad. Pr. 1967 without ISBN 0 12 528150 1
Long the standard work on its subject, but written before the theorem was proven. Has a wealth of other graph theory material.
S. Fiorini and R. J. Wilson,
Edge-colourings of graphs
(Research notes in math. 16), Pitman 1977, ISBN 0 273 01129 4
The first ever book devoted to edge-colorings, including material previously found only in Russian language journal articles.
Thomas L. Saaty and Paul C. Kainen,
The Four-Color Problem: assaults and conquest,
McGraw-Hill 1977; repr. Dover 1986, ISBN 0 486 65092 8
Wonderfully broad, not only focussing on the now standard route to the Appel-Haken proof but also giving a wealth of other material related to colorings.
Rudolf Fritsch and Gerda Fritsch,
Der Vierfarbensatz, Brockhaus 1994;
The Four-Color Theorem, tra. Julie Peschke,
Springer 1998, ISBN 0-387-98497-6
History of the theorem with biographical cameos by G. Fritsch, thorough topological treatment of plane graph embedding and details of the Appel-Haken proof by R. Fritsch.
Robert A. Wilson,
Graphs, Colourings and the Four-colour Theorem,
Oxford Univ. Pr. 2002, ISBN 0 19 851062 4 (pbk),
http://www.maths.qmul.ac.uk/ raw/graph.htmlhttp://www.maths.qmul.ac.uk/ raw/graph.html
A good general course in graph theory, with special focus on the four-color theorem and details of the Appel-Haken proof.
|Title||colorings of plane graphs|
|Date of creation||2013-03-22 15:10:25|
|Last modified on||2013-03-22 15:10:25|
|Last modified by||marijke (8873)|