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 graphis a graph that can be embedded on a sphere or plane.A plane graphis such a graph together with a choice how to embed it; its facesare the resulting regions of surface separated by edges.

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

In graph theory however there is usually an extra condition a coloring has tosatisfy to be valid. Unless specified otherwise, the condition is thatadjacent items must be given distinct colors — two edges meeting at a vertexmust 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 coloringmaps, 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 beconsidered adjacent it is not enough to just meet at one point. The reason isthat that would make coloring problems uninteresting: divide a region into asmany countries as you want, arranged like a pie chart, and any number of colorswould be required if touching at a point did qualify.

So in a map which has a portion shaped like $\times$, both the North andSouth countries border both the East and West countries, but South doesnot border North so they’re allowed to have the same color, and West islikewise allowed to have the same color as East. Now consider a small borderadjustment from $\times$ to where we’ve added oneextra constraint: now North and South must have different colors. If it waspossible to color the old map with a certain number of colors we can’t becertain we can still color the new map. Conversely however, if we can colorthe new map we can certainly color the old map (using the same colorassignment 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 twonew vertices of valency 3 and a short new stretch of border, adding aconstraint on coloring. Vertices with valency $v>4$ can be given the sametreatment in $v-3$ steps, creating $v-2$ vertices of valency 3 and $v-3$ newpieces of border which only makes the problem harder: if we can still colorthis, we can also color the original.

2-valent vertices are simply funny features along an ongoing borderbetween two countries, and 0-valent vertices funny features within thelandscape. Removing them does not alter the coloring exercise. And finally1-valent vertices create a bridge; we do not want them nor do we want anyother bridges, because at such an edge a country meets itself on theother 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^{𝖸}$ istrivalent (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 isimmediate (any includes all the trivalent ones).  $\circ {}^{\circ }\circ$

Note the lemma does not state either side of the “iff” is true, merelythat they are equivalent. The left-hand side is known as the four-colortheorem; having the right-hand side equivalent to it gives statements ontrivalent graphs a more general importance.

One last point: we will consider the graph drawn on a sphere. Or, what is thesame thing: if we draw it on a plane, we will also consider the infinite outsidearea to be a face. If you were thinking of your graph as a map subdividing afinite continent into countries just call the outside Oceania and color itblue.

This convention too only makes the coloring harder: considering the outside tobe a colorless sea allows countries with a shoreline to be of all four colors,while coloring Oceania (say) blue only allows those countries three differentcolors (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 withonly three colors, such that at each vertex the colors of the three edgesthere 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 beface-colored with 4 colors if and only if it can be edge-colored with 3colors.

We will not give our four colors such poetic names as red or green, insteadthey will be given two-bit labels (0,0) and (0,1) and (1,0) and (1,1), formallyvectors in ${\mathrm{𝖨𝖥}}_2^2$, the vector space of dimension 2 over the finite fieldof order 2.

Edge colors used will be the difference between the face colors oneither side of the edge. Because ${\mathrm{𝖨𝖥}}_2^2$ has characteristic 2, differencesare 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 bitpatterns: addition without internal carry, that is, the xor operation).

Note that the assignment of labels to face colors is quitearbitrary (e.g. $(0,0)$ has no special significance) but theassignment to edge colors is less arbitrary: here $\mathrm{𝟎}=(0,0)$ reallymeans something. It means a border between faces of the same color, exactlythe thing that shouldn’t happen. You could say face colors are“position vectors” (where $(0,0)$ is an arbitrary point) whileedge 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 twoedges 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 wehave $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 meansthey 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 countryyou’re in, and travel the world. At each border, add its edge color to theprevious face color and assign that to the new country. I called edge colorsdifferences rather than sums for that reason: if a journey $\mathrm{\Gamma }$visits faces $\alpha \beta \gamma \mathrm{\dots }\psi \omega$, and the face colors everywherehave 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 withoutcontradiction between all possible journeys, this “potential” $f$ willautomatically have $g$ as its “gradient” as it should. Remains to provethe “integral” is independent of path taken, in other words that circularpaths “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 graphin 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$ impliesvalid $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 inWilson [Wil02], adapted here to use the ${\mathrm{𝖨𝖥}}_2^2$ notation, relies onthe graph being embedded in a plane. For a graph embedded in a sphere thatentails choosing a country and puncturing the sphere in the interior ofthat country; it corresponds to the choice of giving that country the facecolor (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 twocolors (any,1). Such graphs consist of disjoint cycles. In a plane, suchcycles have a well-defined interior and exterior. Every face $\alpha$ has anumber $g^{\prime }$ counting the number of (nested) cycles of $G^{\prime }$ it is inside, andsimilarly 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 facethe 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 by1 from $g^{\prime }$, likewise $e^{\prime \prime }=1$ iff $\beta$ is inside a number of $G^{\prime \prime }$ cyclesthat differs by 1 from $g^{\prime \prime }$. So $\beta$ has color $(r^{\prime }+e^{\prime },r^{\prime \prime }+e^{\prime \prime })$ and weknow $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, inthe 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” qualifierbecause having a cycle in which every vertex is involved means no bridges:for any vertices p and q you can travel between them via theHamiltonian cycle, and back via all different edges using the other half ofthe cycle. That would be impossible with a bridge: pick p and qeither side of the bridge, now two routes between them would have to use thesame 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 onered 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 tobe equivalent to being edge-3-colorable by Tait’s theorem, is also equivalentto admitting a certain kind of vertex-2-coloring. This seems to have beendiscovered 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 differentcolor! 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-coloredwith 3 colors if and only if it can be vertex-colored in the way justexplained.

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 significanceto 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 goingclockwise; $-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 thefollowing sense. If we travel around a face counterclockwise (i.e. alwaysturning left) and $d$ and $e$ are two successive edges joined at vertexp, 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 roundthe 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 couldassign 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 zeroaround the cycle, it consistently assigns edge colors (e.g. edge $e$ againgets color $c$ once around the cycle) and because $h_3$ is never zero, wenever get the same edge color for successive edges.

But this isn’t yet enough. Given an $h_3$ satisfying its rule, we can startreconstructing $g_3$ by this “integration” process. We just saw it workslocally on the level of single face boundary cycles. As with the previoustheorem however, the problem with “integrating” is to prove this can be doneunambiguously on a global scale, for which the topological properties ofgenus 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 adisk, that it doesn’t enclose any isolated area. Its boundary is a simpleclosed 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 singleconnected shaded area inside the boundary and a single connected unshaded areaoutside, and that the boundary is one closed curve. Of course, whilethe outside starts off big, it is reduced to just one face by the time theinside has reached $u-1$ faces.

Proof of lemma: start with one face shaded. At each stage, there will beother faces immediately bordering the area shaded thus far. Choose one,call it $\alpha$. If accreting it to the side of the growing shaded areawould 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 alreadyenclosing an unshaded region, the whole outside. So what is really happeningif $\alpha$ misbehaves is that adding it would split the remaining outsideinto two (or more) pieces. Choose any one of those pieces and let that beour region $\mathrm{\Re }$.

Note that each of those pieces, including $\mathrm{\Re }$, contain some faces thatborder the already shaded area. The way it works is this: The boundary of theshaded 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’tmisbehave; 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 shadedregion, and try adding it. If that would fail too it would be by splittingthe 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 iswholly 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 shadedregion, 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 countrythat 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 oneof its edges and then continue assigning $g_3$ colors based on $h_3$ goinground, 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 ofthe shaded area simply connected means that each new face borders the previousshaded area along a single stretch of boundary (say edges $a\mathrm{\dots }m$ goingcounterclockwise), and this means the portion of the boundary of the new facewhere 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 colorit already has, and go round turning left each time assigning edge colorsbased on $h_3$. This must agree with the colors for $b\mathrm{\dots }m$ we alreadyassigned consistently, and gives new colors for $n\mathrm{\dots }z$ (which are now alsoconsistent 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 edgescolored, validly.  $\circ {}^{\circ }\circ$

It’s a pity there doesn’t seem to be an easy way to find such a vertexcoloring 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, validface-4-colorings and edge-3-colorings of the dodecahedron correspond to avertex-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 andtreat 4 of those 20 vertices differently.

The four-color theorem says every bridgeless trivalent plane graph has a validface-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 nextthing would be a valid something-1-coloring, and it shouldn’t be too hard toprove that things can all be colored with 1 color! Unfortunately, we seem tohave 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 somewhite ($-1$) vertices. Around each face, they sum to 0 (mod 3).

Now consider the following modification: pick any vertex, and replace itby a tiny triangular country. If we give the three new vertices the oppositecolor from the old vertex, the coloring is still valid (in each of the threeadjoining 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 singlevertex. The only way three $+1$ or $-1$ can add to zero (mod 3) is if theywere all of the same sign, so we replace it by one vertex of the oppositesign.

Now suppose we expand all white vertices to black triangles. Or vice versa. Wesaw each single modification leaves a valid vertex coloring valid. So oncewe’re done and only have vertices of the same color, the coloring muststill be valid. That can only mean one thing: every face now has a number ofvertices divisible by 3. Not only the triangles we added, but also theoriginal 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 faceended 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 triangleit replaced. Modifications and their reversals preserve the validity ofvertex-2-colorings, so by the time we have undone every modification the graphis still validly colored.  $\circ {}^{\circ }\circ$

This gives yet another corollary of the four color theorem: that we can alwaysfind 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 vertexin $\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 itsendpoints.

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 dualof $G^{*}$.

To prove that assertion: let p be a vertex of $G$, surroundedby faces $\alpha$, $\beta \mathrm{\dots }$ and with edges $d$, $e\mathrm{\dots }$ radiating fromit. All those edges will be crossed by edges of $G^{*}$ forming a closed cyclebecause 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 noedges of $G$ nearer to p to cross, so the cycle forms the boundary of aface. 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’sformula. $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 unknownnumber $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. Instead of a face-4-coloring, a vertex-4-coloring. Note this is different fromthe vertex-2-coloring in the previous sections; it has the standard constraintthat adjacent vertices must have different colors.

The dual expression of lemma 0 is now that it is sufficient to consider planegraphs 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 in1832, obtained firsts in both mathematics and law, taught mathematics in SouthAfrica until his death in 1899 and also found the time to get involved withrailroad construction and to make his name in botany. One day he noticedsomething when coloring a map of the counties of England — the originalfour-color conjecture. And on 23 October 1852, in London, his brother Frederickasked his own math professor Augustus de Morgan about that observation(“With my brother’s permission”). De Morgan consulted Hamilton (“Astudent of mine asked me to day to give him a reason for a fact which I didnot know was a fact — and do not yet.”). The latter didn’t think much ofit 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 hisflawed 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.