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.

A (face, edge, vertex etc.) coloring is just a mapping from the relevant set of items to a small set of other things traditionally given the names of colors.

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.

Face colorings

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 $\times$, 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 $\times$ 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 $G$ (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 $v>4$ can be given the same treatment in $v-3$ steps, creating $v-2$ vertices of valency 3 and $v-3$ 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 $G^{𝖸}$ is trivalent (cubic). And if it can be $n$-colored (for any $n$), then so can $G$. 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).  $\circ {}^{\circ }\circ$

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.

Edge colorings

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 ${\mathrm{𝖨𝖥}}_2^2$, 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 ${\mathrm{𝖨𝖥}}_2^2$ 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. $(0,0)$ has no special significance) but the assignment to edge colors is less arbitrary: here $\mathrm{𝟎}=(0,0)$ 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 $(0,0)$ is an arbitrary point) while edge colors are “free vectors”, differences between position vectors.

Proof of $⟹$: let $F$ and $E$ be the sets of faces and edges, let $f:F\to {\mathrm{𝖨𝖥}}_2^2$ be a valid face-4-coloring, and $g:E\to {\mathrm{𝖨𝖥}}_2^2$ the edge coloring we are trying to construct from $f$. Let $e$ be any edge, and $\alpha$ and $\beta$ the faces it separates. Now $f$ being valid means $f(\alpha )\ne f(\beta )$ so $g(e)=f(\alpha )-f(\beta )\ne \mathrm{𝟎}$. This means $g$ really is an edge-3-coloring $g:E\to {\mathrm{𝖨𝖥}}_2^2\setminus \{\mathrm{𝟎}\}$.

It is also easy to see $g$ is a valid coloring: let $d$ and $e$ be any two edges meeting at vertex p say, and let $\alpha$, $\beta$ and $\gamma$ be the three faces found around p such that $e$ separates $\alpha$ and $\beta$, and $d$ separates $\alpha$ and $\gamma$. By $f$ being valid we have $f(\beta )\ne f(\gamma )$ from which $g(e)=f(\beta )-f(\alpha )\ne f(\gamma )-f(\alpha )=g(d)$.  $\circ {}^{\circ }\circ$

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 $\mathrm{𝟎}$ in a valid edge-3-coloring, a result we will use.

To construct $f$ from $g$ 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 $\mathrm{\Gamma }$ visits faces $\alpha \beta \gamma \mathrm{\dots }\psi \omega$, and the face colors everywhere have to be such that the edges crossed have colors $f(\beta )-f(\alpha )$, $f(\gamma )-f(\beta )$, … $f(\omega )-f(\psi )$ then the color $f(\omega )$ reached should be $f(\alpha )+\sum$ colors of edges crossed.

So we construct $f$ by “integrating” $g$ (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” $f$ will automatically have $g$ 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 $f$ implies valid $g$) is true in surfaces of any genus. For the reverse half (valid $g$ implies valid $f$) 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 ${\mathrm{𝖨𝖥}}_2^2$ 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 $G^{\prime }$ formed by edges of the two colors (1,any) is regular 2-valent. So is the subgraph $G^{\prime \prime }$ 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 $\alpha$ has a number $g^{\prime }$ counting the number of (nested) cycles of $G^{\prime }$ it is inside, and similarly a number $g^{\prime \prime }$ with respect to $G^{\prime \prime }$.

Let $r^{\prime }$ and $r^{\prime \prime }$ be the residues of $g^{\prime }$ and $g^{\prime \prime }$ (mod 2). Give the face the color $(r^{\prime },r^{\prime \prime })$. This is clearly a face-4-coloring. And it is valid: to reach any neighbouring face $\beta$ we cross an edge with color $(e^{\prime },e^{\prime \prime })$ where $e^{\prime }=1$ iff $\beta$ is inside a number of $G^{\prime }$ cycles that differs by 1 from $g^{\prime }$, likewise $e^{\prime \prime }=1$ iff $\beta$ is inside a number of $G^{\prime \prime }$ cycles that differs by 1 from $g^{\prime \prime }$. So $\beta$ has color $(r^{\prime }+e^{\prime },r^{\prime \prime }+e^{\prime \prime })$ and we know $e^{\prime }$ and $e^{\prime \prime }$ are not both zero.  $\circ {}^{\circ }\circ$

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 $m$ equals $3n/2$ where $n$ is the number of vertices. But $m$ is an integer, so $n$ is even.

Proof of lemma: the Hamiltonian cycle, having $n$ vertices, also has $n$ 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.  $\circ {}^{\circ }\circ$

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 $+1$ and $-1$ 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 $g_3$ be this new relabeled verion of the old $g$.

We construct a vertex coloring $h_3:V\to \{+1,-1\}$ from $g_3$ as follows: assign color $+1$ to a vertex if the edges there have colors 0, 1, 2 going clockwise; $-1$ if counterclockwise. If the edge coloring $g_3$ is valid, it is possible to define an $h_3$ 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 $d$ and $e$ are two successive edges joined at vertex p, then $g_3(e)-g_3(d)=h_3(\mathrm{\text{p}})$. If instead we turn right to edge $x$ say, we get $g_3(x)-g_3(d)=-h_3(\mathrm{\text{p}})$.

Proof of $⟹$: Based on $g_3$, define $h_3$ as above. To prove it is valid. Pick any face $\alpha$, and any edge $e$ in it, let $g_3(e)=c$. Go round the face counterclockwise one whole cycle. Now

$$c+\sum _{\mathrm{V}\in \alpha }h(\mathrm{\text{v}})=c$$

(mod 3). Which proves the sum of $h_3$ values around the cycle is zero.  $\circ {}^{\circ }\circ$

The same argument works in reverse: if $h_3$ is a valid vertex coloring then, in any one cycle, we could assign an arbitrary color $c$ to an edge $e$ and, going round counterclockwise finding vertices p, q… we could assign to the edges after $e$ the colors $c+h_3(\mathrm{\text{p}})$, $c+h_3(\mathrm{\text{p}})+h_3(\mathrm{\text{q}})$, and so on. Because $h_3$ sums to zero around the cycle, it consistently assigns edge colors (e.g. edge $e$ again gets color $c$ once around the cycle) and because $h_3$ is never zero, we never get the same edge color for successive edges.

But this isn’t yet enough. Given an $h_3$ satisfying its rule, we can start reconstructing $g_3$ 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 $u$ faces on a genus 0 surface, it is possible to enlarge a collection of 1 face to $u-1$ 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 $u-1$ 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 $\alpha$. 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 $\alpha$ misbehaves, that adding it would enclose (one or more) unshaded region(s) $\mathrm{\Re }$. Of course on a sphere we are already enclosing an unshaded region, the whole outside. So what is really happening if $\alpha$ 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 $\mathrm{\Re }$.

Note that each of those pieces, including $\mathrm{\Re }$, contain some faces that border the already shaded area. The way it works is this: The boundary of the shaded region has $k$ stretches where it borders $\alpha$, and $k⩾1$ because $\alpha$ was chosen as a face that borders the shaded area. If $k=1$ it doesn’t misbehave; if $k>1$ then adding it would split the new outside into $k$ regions: in between the $k$ stretches where the shaded area borders $\alpha$ there are $k$ stretches where each time it would border one of those regions.

Choose a face $\beta$ from the faces of $\mathrm{\Re }$ 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 $\alpha$ and call it ${\mathrm{\Re }}^{\prime }$. Because it does not include $\alpha$, it is wholly contained within one of the regions adding $\alpha$ would have created, namely $\mathrm{\Re }$. In fact ${\mathrm{\Re }}^{\prime }\subseteq \mathrm{\Re }\setminus \{\beta \}$ i.e. it has at least one fewer country than $\mathrm{\Re }$.

Choose a face $\gamma$ from the faces of ${\mathrm{\Re }}^{\prime }$ that border the shaded region, if this doesn’t work either choose a ${\mathrm{\Re }}^{\prime \prime }$ that does not contain $\beta$, and so on.

Now $\mathrm{\Re }$ only has finitely many faces, and $|\mathrm{\Re }|>|{\mathrm{\Re }}^{\prime }|>|{\mathrm{\Re }}^{\prime \prime }|\mathrm{\dots }$. 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.  $\circ {}^{\circ }\circ$

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 $g_3$ colors based on $h_3$ 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 $a\mathrm{\dots }m$ going counterclockwise), and this means the portion of the boundary of the new face where the edges ($n\mathrm{\dots }z$ say) don’t have colors yet is also a single stretch.

This means we can edge-color the additional face validly: give $a$ the color it already has, and go round turning left each time assigning edge colors based on $h_3$. This must agree with the colors for $b\mathrm{\dots }m$ we already assigned consistently, and gives new colors for $n\mathrm{\dots }z$ (which are now also consistent with the rest) and gives the same color again to $a$ because $h_3$ is valid.

Once we have covered $u-1$ faces, the last face already has all its edges colored, validly.  $\circ {}^{\circ }\circ$

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: $3n$-gon faces

Consider a valid vertex-2-coloring $h_3$, with some black ($+1$) and some white ($-1$) 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 $\pm 1$ is replaced by two $\mp 1$ 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 $+1$ or $-1$ 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.  $\circ {}^{\circ }\circ$

Proof of $⟸:$ We are given such a sequence of modifications where every face ended up as a $3n$-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.  $\circ {}^{\circ }\circ$

This gives yet another corollary of the four color theorem: that we can always find such a modication to $3n$-gon faces.

Duals

The dual $G^{*}$ of a bridgeless plane graph $G$ is formed as follows: place one vertex of $G^{*}$ inside each face of $G$. For each edge $e$ of $G$, separating faces $\alpha$ and $\beta$, draw one edge of $G^{*}$ from its vertex in $\alpha$ to its vertex in $\beta$, in such a way that the only edge of $G$ it crosses is $e$, and so that it crosses $e$ at a point other than its endpoints.

This construction creates faces of $G^{*}$ that each enclose one vertex of $G$ and every one of those vertices is thus enclosed, making $G$ likewise a dual of $G^{*}$.

To prove that assertion: let p be a vertex of $G$, surrounded by faces $\alpha$, $\beta \mathrm{\dots }$ and with edges $d$, $e\mathrm{\dots }$ radiating from it. All those edges will be crossed by edges of $G^{*}$ forming a closed cycle because they connect the vertices of $G^{*}$ placed inside $\alpha$, $\beta \mathrm{\dots }$ going round. There are no other edges of $G^{*}$ crossing our edges, and no edges of $G$ nearer to p to cross, so the cycle forms the boundary of a face. This shows every vertex of $G$ has a dual face of $G^{*}$.

To show every face of $G^{*}$ is now accounted for, we can invoke Euler’s formula. $G$ has $n$ vertices, $m$ edges, $f$ faces, with $n-m+f=2$. For $G^{*}$ we have by construction $n^{*}=f$ vertices, $m^{*}=m$ edges, and an unknown number $f^{*}$ of faces. By the previous argument there are at least the $n$ faces with vertices of $G$ in it. But by $n^{*}-m^{*}+f^{*}=2$ (and $n^{*}=f$ and $m^{*}=m$ and $n-m+f=2$) $f^{*}$ must equal that $n$.  $\circ {}^{\circ }\circ$

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 dual expression of lemma 0 is now that it is sufficient to consider plane graphs where every face is triangular (the dual of the $\times$ to machinations is tiling up a $v$-gon into $v-2$ triangles).

History

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.

Title	colorings of plane graphs
Canonical name	ColoringsOfPlaneGraphs
Date of creation	2013-03-22 15:10:25
Last modified on	2013-03-22 15:10:25
Owner	marijke (8873)
Last modified by	marijke (8873)
Numerical id	8
Author	marijke (8873)
Entry type	Topic
Classification	msc 05C15
Related topic	FourColorConjecture
Related topic	TaitColoring
Related topic	KempeChain