betaFeedback

WorksComputer Science

Four-Coloring Planar Graphs in Linear Time

Abstract

The famous Four Color Theorem (4CT) states that any planar graph can be colored with four colors, but how do we find a 4-coloring? In our previous paper [FOCS'26], we presented a simple combinatorial algorithm to 4-color planar graphs in O(nlog⁡n)O(n\log n) time. We improve it here to O(n)O(n) time, which is optimal. The algorithm from our previous paper is based on proving that every planar triangulation has a linear number of reducible configurations or obstructing cycles. The bottleneck for the algorithm is that we need O(log⁡n)O(\log n) Kempe changes to extend a recursive 4-coloring to the reducible configurations. Each Kempe change can involve a constant fraction of the graph and takes linear time. Here we show that all O(log⁡n)O(\log n) Kempe changes can be identified and implemented in O(n)O(n) time. The idea is to spend O(n)O(n) time to preprocess the graph so that we can identify and simulate each good Kempe change in O(n/log⁡n)O(n/\log n) amortized time. Thus, we implement all O(log⁡n)O(\log n) Kempe changes in O(n)O(n) total time. Based on this, we implement the whole 4-coloring in linear time. We note that creating such a representation for fast identification and simulation of the right Kempe changes is a challenge of data structures, unlike the previous paper that builds on a new graph theoretic understanding of reducible configurations.

Introduction

The celebrated Four Color Theorem (4CT) was conjectured by Francis Guthrie in 1852 (see [14, 20] for some of the early history), and remained open for more than 100 years, until Appel and Haken found a proof [2, 4] in 1976. The theorem states that every planar map or graph with no loops can be colored with four colors. So 4-coloring is always possible, but how do we 4-color a concrete planar graph? There is no easy answer. In fact, historically, it has been so complicated that it has led to many proposed counterexamples to 4CT.

Robertson, Sanders, Seymour, and Thomas [17, 18] found a simpler proof and proved in 1997 that a 4-coloring can be found in quadratic time.

In a preceding paper [9], we proved that 4-coloring can be done in O(nlog⁡n)O(n \log n) time. In this paper, we show how to do it in linear time, that is,

Theorem 1 We can 4-color a planar graph of order nn in O(n)O(n) time.

This optimal time bound builds on the graph-theoretic results from [9] which yielded a combinatorial O(nlog⁡n)O(n \log n) time solution. Our improvement to O(n)O(n) time is based on a new efficient data structure. More precisely, we use the word RAM model with word length Θ(log⁡n)\Theta(\log n). The unit-cost operations are the standard AC0\mathrm{AC}^{0} operations available in an imperative programming language such as C [12]: direct and indirect addressing, conditional jump, addition, bitwise Boolean operations, and shifts (called the Practical RAM in [15]).

Graph theoretic foundations

In order to describe our contribution in more detail, we first review the relevant concepts and results from previous work on 4CT. If we just say coloring, we mean a proper 4-coloring with colors 1, 2, 3, 4.

By a planar triangulation (or just triangulation) we mean a (simple) graph embedded in the 2-sphere, all of whose faces are triangles. The 4CT says that any planar graph can be 4-colored, but since triangulations can only make coloring harder, it suffices to consider planar triangulations. We say a cycle CC is obstructing if it is of length at most 4 with at least one vertex on each side, or of length 5, with at least 2 vertices on each side. Birkhoff proved in [6] that a minimal counterexample to 4CT has no obstructing cycles.

Kempe chains and Kempe changes Given a 4-colored graph GG and two colors aa, bb, an abab-colored component is a component of the subgraph of GG induced by the vertices of color aa or bb. To define Kempe chains and changes, we first need to decide a color pairing {a,b}\{a,b\} and {c,d}\{c,d\} with {a,b,c,d}={1,2,3,4}\{a,b,c,d\} = \{1,2,3,4\}. The Kempe chains are now the abab- and cdcd-colored components. For a Kempe change, we swap the colors on a subset of the Kempe chains; that is, for an abab-colored component, a swap switches aa and bb, and on a cdcd-colored component, it switches cc and dd. Such a Kempe change preserves a proper 4-coloring. The use of Kempe changes was pioneered by Kempe in [11], and has been used in all later correct proofs of 4CT.

Configurations A key concept from the classic proof of the 4CT [3, 17] is that of a reducible configuration. Roughly speaking, a reducible configuration is a locally defined configuration such that, if it appears in a triangulation, it cannot be a minimal counterexample to 4CT. To define reducible configurations formally, we first need to define configurations.

Sometimes we view the triangulation GG we want to color as embedded in the plane, and we may or may not treat one of the faces as the outer face. A near-triangulation is a connected graph embedded in the plane such that all facial walks, except for the outer face, are triangles. This includes the trivial near-triangulations consisting of a single edge or vertex.

By a configuration we mean a pair (Z,δ)(Z,\delta), where ZZ is a near-triangulation and δ:V(Z)→N\delta: V(Z) \to\mathbb{N} is the degree function satisfying the following condition: if v∈V(Z)v \in V(Z) is a vertex that is not on the boundary of ZZ, then δ(v)=dZ(v)\delta(v) = d_Z(v); otherwise δ(v)>dZ(v)\delta(v) > d_Z(v). Moreover, if vv is a cut-vertex of ZZ, then δ(v)=dZ(v)+2\delta(v) = d_Z(v) + 2.

We say that a plane triangulation GG contains the configuration (Z,δ)(Z,\delta) if ZZ is embedded in GG such that every inner triangular face of ZZ is also a face in GG, and all triangular faces of ZZ have the same orientation in GG. Moreover, we require that the degree of each vertex v∈V(Z)v \in V(Z) in GG is equal to δ(v)\delta(v), that is dG(v)=δ(v)d_G(v) = \delta(v). Finally, if vv is a cut vertex in ZZ, its two neighbors outside ZZ in GG are non-consecutive around vv. We say that ZZ, or the configuration (Z,δ)(Z,\delta), is induced in GG if ZZ is an induced subgraph of GG.

If (Z,δ)(Z,\delta) is a configuration, the free completion of (Z,δ)(Z,\delta) is the near-triangulation Z^\widehat{Z} obtained from ZZ by adding a cycle R=R(Z)R = R(Z), disjoint from ZZ and joining vertices on the outer face of ZZ to RR in such a way that RR becomes the outer face of the near-triangulation Z^\widehat{Z} and such that Z^\widehat{Z} contains (Z,δ)(Z,\delta). See the illustration in Figure 1.

A D-reducible configuration with a cut-vertex and its free completion

Figure 1. A D-reducible configuration (Z,δ)(Z,\delta) with a cut-vertex and its free completion.

The length of the cycle RR is precisely

∣R∣=∑v∈V(Z)(δ(v)−dZ(v))−t=∑v∈V(Z)δ(v)−2∣E(Z)∣−t,|R| = \sum_{v \in V(Z)}\left(\delta(v) - d_Z(v)\right) - t = \sum_{v \in V(Z)}\delta(v) - 2|E(Z)| - t,

where tt is the length of the outer facial walk of ZZ. The cycle R=R(Z)R = R(Z) is called the ring of the free completion.

Reducible configurations Suppose that GG contains an induced configuration (Z,δ)(Z,\delta). Since ZZ is induced in GG, the triangulation GG contains the free completion of ZZ, possibly with some vertices and edges on R(Z)R(Z) that may be identified in GG. Equivalently, when ZZ is induced, the embedding ϕ\phi of ZZ into GG can be extended to a homomorphism ϕ^\widehat{\phi} from Z^\widehat{Z} into GG, but this homomorphism may not be 1-1 on R(Z)R(Z).

Every 4-coloring ψ0\psi_0 of G−V(Z)G - V(Z) induces a 4-coloring of the ring R=R(Z)R = R(Z) in the free completion. If this 4-coloring can be extended to a 4-coloring ψ1\psi_1 of Z^\widehat{Z}, then the combination of ψ0\psi_0 and ψ1\psi_1 gives a 4-coloring of GG. In the proof of 4CT, special configurations are shown to be reducible. This happens if any 4-coloring ψ0\psi_0 can be changed (by using a sequence of Kempe changes in G−V(Z)G - V(Z)) so that the resulting coloring extends from RR to Z^\widehat{Z}. We describe the precise definition and the process related to Kempe changes next.

We say that a coloring ψ\psi of RR is 0-extendible (or just extendible) to ZZ if it can be extended to a coloring of Z^\widehat{Z}. For each integer i>0i > 0 we say that ψ\psi is ii-extendible to ZZ if it is either (i−1)(i - 1)-extendible or the following holds: If G′G' is an arbitrary plane graph containing the ring RR as a facial cycle and ψ\psi is any 4-coloring of G′G' extending ψ\psi, then there is a Kempe change of ψ\psi such that the resulting 4-coloring on RR after making the Kempe change is an (i−1)(i - 1)-extendible 4-coloring of RR. We define the reducibility level (or just level) of ψ\psi as the minimum ii such that ψ\psi is ii-extendible. A Kempe change in G−V(Z)G - V(Z) is called an improving Kempe change if it changes the coloring of RR to a lower level.

We say that the configuration (Z,δ)(Z,\delta) is Di\mathrm{D}^{i}-reducible if every 4-coloring of its ring is ii-extendible, and DD-reducible means Di\mathrm{D}^{i}-reducible for some finite ii. Exercising the definition, we have

Lemma 2 A single vertex of degree 3 or 4 is DD-reducible. It is 0-extendible if the degree is 3 and 1-extendible if the degree is 4.

Proof If the vertex has degree 3, we can remove it, color the remaining graph, and then put it back, assigning a color not used in its ring. If the vertex vv has degree 4, we also remove it and color the rest. If the ring has at most three colors, we are done as above. Otherwise, we need a Kempe change. Let v0,…,v3v_0,\ldots,v_3 be the ring vertices in the order they appear around vv. Look at the Kempe chain AA of v0v_0 induced by the colors of v0v_0 and v2v_2. If AA does not include v2v_2, we simply perform the Kempe change on AA. Otherwise, AA connects v0v_0 and v2v_2, so we can perform a Kempe change on v1v_1 to give it the same color as v3v_3. In each case, the modified coloring can be extended to vv. The proof for the degree-4 case goes back to Kempe [11].

It is easy to see [1, 7] that a minimum counterexample to 4CT cannot contain D-reducible configurations.

Note that a D-reducible configuration (Z,δ)(Z,\delta) may be contained as a non-induced subgraph of a triangulation GG. In that case we may not be able to use Kempe-changes to extend a 4-coloring of G−V(Z)G - V(Z) to ZZ. Nevertheless, we still say that the subgraph ZZ in GG is D-reducible.

We note that many works on 4CT, including the first proof in [3], use a more general notion of reducibility, called C-reducibility introduced by Franklin [7] and used in [3] and [17]; see also [1]. With C-reducibility, we do not just remove V(Z)V(Z) from GG, but we also do some contractions on the resulting face. The proofs of 4CT in [3, 17] show that any triangulation contains either an obstructing cycle or a D- or C-reducible configuration from a given finite set of such configurations. However, [19] proved that a set of D-reducible configurations suffices, which will be important to us.

In this paper, we mostly discuss configurations (Z,δ)(Z,\delta) with a given embedding in GG, where for each vertex v∈V(Z)v \in V(Z), δ(v)=dG(v)\delta(v) = d_G(v). Therefore, we will often identify such a configuration with the embedded near-triangulation ZZ.

A quadratic algorithm. In [18], the authors derive a quadratic-time 4-coloring algorithm.

The proofs above imply that for any triangulation, we can find either an obstructing cycle or a reducible configuration in linear time.

If we find a reducible configuration ZZ, we reduce it and color the rest by induction. This gives a coloring of the ring RR. If it is an ii-extendible configuration, then we may have to perform up to ii improving Kempe changes before we can extend the coloring to the original ZZ.

To tell if a Kempe chain is improving, we need to know the level of all colorings of the ring RR. This is only a constant amount of information, since we only have a constant number of reducible configurations of constant size.

Also note that we only know that an improving Kempe change exists, but which one works depends on the graph and the coloring outside the ring. Recall that a Kempe change is characterized by color pairing {a,b}\{a,b\} and {c,d}\{c,d\} of colors and a subset of abab- and cdcd-colored Kempe chains on which the two colors are swapped. The swapping only affects the coloring of the ring if the Kempe chain intersects the ring. This means that there are fewer than 3⋅2∣R∣=O(1)3 \cdot2^{|R|} = O(1) relevant Kempe changes to check, and we apply the first improving one we find. We can implement all of this in linear total time.

[18] also shows how we can benefit from obstructing cycles. The general conclusion is that we can reduce the problem size by an additive constant in linear time, so the overall algorithm is quadratic.

The main bottleneck in the above approach is the Kempe changes. The interaction between different Kempe chains can be very complicated. Each Kempe chain can be of linear size, and if, for example, we first perform a Kempe change using color pairs aa, bb and cc, dd, then it can affect the acac, adad, bcbc, and bdbd-colored Kempe chains. So, multiple Kempe changes can be quite chaotic. It seems hopeless to update the information about Kempe chains in sublinear time.

Our previous work

As mentioned earlier, our optimal O(n)O(n) coloring is an efficient implementation of our previous combinatorial O(nlog⁡n)O(n \log n) algorithm from [9]. In the following we review the relevant parts of [9]. Let us recall that two subgraphs XX and YY of GG touch if either V(X)∩V(Y)≠∅V(X) \cap V(Y) \ne\varnothing, or there is an edge xy∈E(G)xy \in E(G) with x∈V(X)x \in V(X) and y∈V(Y)y \in V(Y).

Linear number of reducible configurations The main result from our preceding paper [9] is as follows.

Theorem 3 ([9]). There is a linear-time algorithm that, given any triangulation GG, finds one of the following:

(a) A linear number of pairwise non-touching induced D-reducible configurations in GG, each of which from a given set D\mathcal{D} of size 8202.

(b) A linear number of non-touching obstructing cycles in GG.

All vertices in the above-mentioned reducible configurations or obstructing cycles have degree at most 12 in GG. Moreover, for the reducible configurations in D\mathcal{D}, the maximal ring size is 18 and the maximal reducibility level is 25.

Note that prior to [9] there was not even an existential proof that a triangulation had more than one reducible configuration or obstructing cycle (which does suffice for 4CT).

An O(nlog⁡n)O(n \log n) recursion Based on Theorem 3, [9] derived an O(nlog⁡n)O(n \log n) time 4-coloring algorithm for a planar triangulation GG of order nn. For this, it suffices that we can construct in O(nlog⁡n)O(n \log n) time a planar triangulation HH that is smaller by a constant factor, color HH recursively, and use this coloring to color GG in O(nlog⁡n)O(n \log n) additional time.

In case (b) of Theorem 3, where we get a linear number of non-touching obstructing cycles, [9] did the recursive step in linear time. The bottleneck in [9] is case (a) where the recursive step takes O(nlog⁡n)O(n \log n) time. Below we discuss this case.

D-reducible configurations. Suppose as in (a) that we get Ω(n)\Omega(n) non-touching induced D-reducible configurations from D\mathcal{D} in GG. In the quadratic-time algorithm, we would just handle one of them in linear time, but here we will handle all of them in O(nlog⁡n)O(n \log n) time. Below, we first show this using randomization.

More specifically, our first obvious step is to remove all the reducible configurations from the graph. This removes Ω(n)\Omega(n) vertices. Next, using new auxiliary edges, we triangulate all the faces inside their now empty rings. Then we recursively color the resulting reduced triangulation, which has a constant factor fewer vertices.

Having colored the reduced triangulation recursively, we restore the original triangulation exactly as it was, removing the auxiliary edges and putting back all the reducible configurations. However, we keep the recursive coloring, which is now a 4-coloring of all vertices outside the reducible configurations. The reducible configurations, while uncolored, have all their rings colored. This follows because they are non-touching, implying that the ring of one reducible configuration does not intersect any other reducible configuration. Kempe chains and changes only apply to the colored vertices.

A randomized approach We will now start doing random Kempe changes on the colored vertices. If the ring RR of a non-colored configuration ZZ gets a 0-extendible coloring, then we extend this 4-coloring of RR to ZZ, and then ZZ is no longer among the non-colored configurations.

In general, if the coloring of a ring is ii-extendible, then we may have to do ii improving Kempe changes to make it 0-extendible. We know from Theorem 3 that all colorings of the rings of our reducible configurations are 25-extendible. Each Kempe change may affect most of the graph, so we cannot afford to do this for one configuration at a time. However, we claim that random Kempe changes are expected to be improving for a constant fraction of the non-colored configurations, and this leads to the following very simple algorithm.

While there is a non-colored configuration, we repeat the following two steps:

  1. Make a random Kempe change. First, we randomly decide the color pairing abab and cdcd that will be used by the Kempe chains, that is, the Kempe chains considered are the abab- and cdcd-colored components. These partition all colored vertices. Next, for every abab-colored and every cdcd-colored component, we toss a coin to decide whether to swap its colors in the random Kempe change.

  1. For all non-colored components ZZ whose ring coloring became 0-extendible, we extend the coloring to ZZ.

We claim that this algorithm terminates after O(log⁡n)O(\log n) iterations with high probability. To prove this, we consider an arbitrary non-colored configuration ZZ, and argue that its ring coloring will become 0-extendible within O(log⁡n)O(\log n) rounds with high probability. The result then follows by a union bound.

Consider the iterations from the perspective of any given reducible configuration ZZ with ring RR. If ZZ is non-colored, it wants a sequence of at most 25 improving Kempe changes. As discussed in the quadratic algorithm, an improving Kempe change requires the right color pairing abab and cdcd. There is a 1/31/3 chance that a random choice is right since the pairs are determined just by the pairing of color 1. Now the improvement only depends on the color change (color swap or no-swap) of the disjoint abab and cdcd-colored components (Kempe chains) intersecting the ring RR, of which there are at most ∣R∣≤18|R| \le18. A random Kempe change is thus improving for ZZ with probability at least 13⋅2−18\frac{1}{3}\cdot2^{-18}. We need at most 25 such consecutive improvements for ZZ for the ring to become 0-extendible. The probability of this success for ZZ is at least p=1/(3⋅218)25=Ω(1)p=1/(3\cdot2^{18})^{25}=\Omega(1).

The above fails for ZZ if we make a Kempe change that is non-improving for ZZ before RR becomes 0-extendible, but if it fails, we still have a coloring of RR, and any coloring of RR is 25-extendible1. If we now do r×25r\times25 iterations, then the probability that we fail to color ZZ is at most (1−p)r<e−pr(1-p)^r<e^{-pr}. With 50p−1ln⁡n50p^{-1}\ln n iterations, this is at most 1/n21/n^2. A union bound implies that all configurations succeed within 50p−1ln⁡n50p^{-1}\ln n iterations with probability at least 1−1/n1-1/n.

Derandomization using method of conditional expectations Using the method of conditional expectations, we derandomize the random choice of Kempe changes above. The derandomization always makes the greedy choice maximizing the expected number of configurations that become 0-extendible. In particular, it will always get at least one 0-extendible configuration within 25 Kempe changes. We will now start doing Kempe changes on the colored vertices. If the ring RR of a non-colored configuration ZZ has a 0-extendible coloring, we extend this 4-coloring of RR to ZZ, and ZZ is no longer among the non-colored configurations (strictly speaking, (Z,dG)(Z,d_G) is the reducible configuration).

The main step is to show that we can deterministically find a Kempe change that improves the level of coloring for a constant fraction of the rings. The key is to prove the following lemma:

Lemma 4 ([9]) Let Z1,…,ZqZ_1,\ldots,Z_q be some (not necessarily all) non-colored reducible configurations in a triangulation GG that is 4-colored except for the remaining non-colored configurations. The colorings of their rings R1,…,RqR_1,\ldots,R_q are not yet 0-extendible.

We can then deterministically, in linear time, find and execute a Kempe change that improves at least a fraction p=13⋅218p = \frac{1}{3\cdot2^{18}} of the rings, and also tell which rings got improved.

Proof. We assume that for every one of our reducible configurations D∈DD \in\mathcal{D} (c.f. Theorem 3), we store the Kempe level of each coloring of its ring. This is a huge constant amount of information, but we need it to determine if a given Kempe change will improve.

For each of the three color combinations, that is, for a∈{2,3,4}a \in\{2,3,4\}, we use the color pairs {1,a}\{1,a\} and {2,3,4}∖{a}\{2,3,4\} \setminus\{a\}, and we identify all the bi-colored Kempe chains. Each vertex now knows which Kempe chain it belongs to.

We now consider the perspective of a given ring RiR_i. Its coloring is only affected by the swap or no-swap of the Kempe chains intersecting it, and there are at most ∣Ri∣≤18|R_i| \le18 such Kempe chains. We now consider all combinations of swap and no-swap for each intersecting Kempe chain. We know which vertices are involved, hence the effect on the coloring, so we can check if a Kempe change following a given combination of intersecting swap/no-swap is improving.

We repeat this for all three color combinations, and for each ring we know at least one color combination and a corresponding intersecting swap/no-swap combination improve the coloring; we pick one such combination for each ring RiR_i.

For the next Kempe change, if we picked both the color combination and the swap/no-swap for each Kempe chain uniformly at random, then the probability that the change was improving for RiR_i would be at least 1/(3⋅2∣Ri∣)≥p=1/(3⋅218)1/(3 \cdot2^{|R_i|}) \ge p = 1/(3 \cdot2^{18}), and hence we would expect a fraction pp of all rings to get improved.

We can get an improvement for at least a fraction pp of the rings using the method of conditional expectation as described below.

At the beginning, all our rings are “live”. For each ring, we know the color pair combination for the improving Kempe change, and we pick the color pair that works for most rings. Only the rings that get their color combination stay alive; the rest will “die”. We know that at least 1/3 stay alive.

We now go through each Kempe chain using the selected color pairs and decide whether to swap the colors. A ring RiR_i only stays live as long as all decided swaps were as it wanted them. If the number of undecided Kempe chains intersecting RiR_i is uiu_i, and if all remaining choices were made at random, then the probability that RiR_i would survive till the end is 2−ui2^{-u_i}. Thus, conditioned on decisions made, the expected number of survivors is

∑Ri is still live2−ui,where ui is the number of undecided chains intersecting Ri.(1)\sum_{R_i\ \mathrm{is\ still\ live}} 2^{-u_i},\quad\text{where } u_i \text{ is the number of undecided chains intersecting } R_i. \tag*{(1)}

We can now pick any undecided Kempe chain XX. We know that one of the two choices — swap or no-swap — will not decrease the conditional expectation, and we can determine which one it is by considering only the live rings that intersect XX. We make a non-decreasing choice for one Kempe chain at a time. Since each ring only intersects a constant number of Kempe chains (at most 18), the total time over all Kempe chains is linear. Since the conditional expectation is non-decreasing as we make our choices, and since we end up with all Kempe chains decided, we conclude that the final set of live rings is at least as big as the original expectation.

We will now use the above lemma to decide on 25 Kempe changes. We say a ring RiR_i is active if all previous Kempe changes have been improving, and it is not yet 0-extendible. We apply Lemma 4 to all active rings. We know that a fraction pp gets an improving move. For the rings RiR_i whose coloring becomes 0-extendible, we extend the coloring to ZiZ_i. The active rings that got an improving move but are still not 0-extendible remain active. We repeatedly apply Lemma 4 to the active rings, finding a new Kempe change that improves by a factor of pp for the remaining active rings. After 25 repetitions, we know that there are no active rings left, and that at least a fraction p25p^{25} of the original rings have been extended. Conversely, this means that the number of empty rings has been reduced by at least a factor 1−p251-p^{25}.

We now restart with all the empty rings, all of which are 25-extendible. If we started with rr reducible configurations, then after at most log⁡1/(1−p25)r=O(log⁡r)=O(log⁡n)\log_{1/(1-p^{25})} r = O(\log r) = O(\log n) rounds of 25 Kempe changes, we know that no empty rings remain, hence that we have colored the whole original configuration GG.

The recursive step, reducing the problem size by a constant factor, is thus completed in O(nlog⁡n)O(n\log n) time. This suffices for the O(nlog⁡n)O(n\log n) time 4-coloring in [9].

More efficient algorithm To clarify what is needed for a more efficient 4-coloring algorithm, [9] stated that it reduces to the following task:

Task 5 (Color Extension) Let GG be a plane triangulation of order nn with a family Z\mathcal{Z} of Ω(n)\Omega(n) pairwise non-touching induced DD-reducible configurations in the family D\mathcal{D} from [9]. Find a fast algorithm that selects a subfamily Z′⊆Z\mathcal{Z}' \subseteq\mathcal{Z} of size Ω(n)\Omega(n) such that, for any 4-coloring of G∖⋃Z′G \setminus\bigcup\mathcal{Z}', we can (again by the fast algorithm) perform O(log⁡n)O(\log n) Kempe changes that result in a 4-coloring of G∖⋃Z′G \setminus\bigcup\mathcal{Z}' which extends to all of GG.

As described above, using Lemma 4 recursively, [9] solves this task with Z′=Z\mathcal{Z}'=\mathcal{Z} in O(nlog⁡n)O(n\log n) time. Moreover, [9] proves:

Theorem 6 ([9]) If we can solve the Color Extension Task 5 of order nn in time T(n)T(n), then we can 4-color any nn-vertex planar graph in time T∗(n)≤O(n)+T(n)+T∗(n/2)T^*(n) \le O(n)+T(n)+T^*(n/2).

Our contribution: linear time 4-coloring

In this paper, we will prove the following theorem.

Theorem 7 We can solve Task 5 in linear time.

By Theorem 6 we can 4-color any planar graph in linear time, as stated in Theorem 1.

To solve Task 5 in linear time, we need to implement the O(log⁡n)O(\log n) Kempe changes in linear total time. The idea is to spend O(n)O(n) time to preprocess the graph, including the selection of an appropriate subfamily Z′\mathcal{Z}', so that we can identify and simulate each Kempe change in O(n/log⁡n)O(n/\log n) amortized time. Thus, we implement all O(log⁡n)O(\log n) Kempe changes in O(n)O(n) total time.

We note that creating such a representation for fast identification and simulation of good Kempe changes is a challenge of data structures, unlike [9], which focused on a new graph theoretic understanding of reducible configurations. Below we list the basic techniques and challenges.

Tabulation. Not surprisingly, our logarithmic speedup comes from tabulating answers to subproblems that can be coded with 12log⁡n\frac{1}{2}\log n bits, an idea that goes back to the Method of Four Russians [5]. These tables are stored in arrays, viewing the codes as integer indices below n\sqrt{n}. It will be important here that a planar graph on qq vertices can be coded with O(q)O(q) bits [10, 21]. We will therefore be very careful in showing that various subproblems can be coded with planar graphs. The challenge is to translate the tabulated solutions for logarithmic-size problems into a full logarithmic speed-up for 4-coloring.

We note that tabulation has its hard limits in the sense that while space ss can tabulate answers to ss queries, it may be much less useful when the space of queries is larger than ss. A first formal proof of this is found in [16], which considers using space s=nlog⁡O(1)ns = n\log^{O(1)} n to support predecessor queries among nn integers from a range [u][u]. If u=su = s, then we can answer queries in constant time with a trivial table. However, if u=s1.1u = s^{1.1} (1.1log⁡2s1.1\log_2 s bits versus log⁡2s\log_2 s bits for keys in [u][u]), then [16] proves that the optimal query time is Θ(log⁡log⁡n)\Theta(\log\log n) even in the powerful cell-probe model for static data structures with unlimited preprocessing time.

rr-divisions. To organize the flow of information, we shall use the recursive rr-divisions from [8, 13]. Here, an rr-division of a planar graph divides it into O(n/r)O(n/r) planar subgraphs, each of size at most rr and boundary of size O(r)O(\sqrt{r}). From a tabulation perspective, r=Θ(log⁡n)r = \Theta(\log n) is interesting because the whole subgraph can be coded with Θ(log⁡n)\Theta(\log n)-bits, but r=Θ(log⁡2n)r = \Theta(\log^2 n) is also of interest because the boundary is a planar graph that can be coded with Θ(log⁡n)\Theta(\log n)-bits.

The challenge. Our challenge is that we need to code not just the regions and their boundaries. To get a deterministic algorithm, we must collect information on all Kempe chains to determine, for each, whether swapping it maximizes the conditional expectation in (1). This basically implies finding out how many of the live reducible configurations want each Kempe chain swapped versus not swapped. For a region in an rr-division, the boundary may intersect Θ(r)\Theta(\sqrt{r}) Kempe chains, but we also have swap/no-swap O(log⁡r)O(\log r)-bit counters from all live configurations. Even if we are the most optimistic, we need Θ(rlog⁡r)\Theta(\sqrt{r}\log r) bits of information to cross the boundary. For r=log⁡2n/log⁡log⁡nr = \log^2 n/\log\log n, this is Θ(log⁡nlog⁡log⁡n)\Theta(\log n\sqrt{\log\log n}), which is more than we can tabulate, yet we cannot afford to use a combinatorial algorithm since the total size of all these boundaries is O(n/r)=O(nlog⁡log⁡n/log⁡n)O(n/\sqrt{r}) = O(n\sqrt{\log\log n}/\log n) and we only have O(n/log⁡n)O(n/\log n) time available.

The main idea to resolve this bottleneck will be to use codes based on appropriate planar graphs to control how tabulation can more efficiently transfer information between arrays of counters. The structural information coded in these planar graphs fits within the tabulation budget even when the counter arrays do not. We divide the counter arrays into smaller segments so that we with a single table look-up can process one source segment and one target segment at a time using the structural information and the previously chosen swap decisions. In the intermediate range of region sizes, the total number of these segment-pair operations is small enough to preserve the required O(n/log⁡n)O(n/\log n) time bound. Section 3.1 gives the details.

The Use of Generative AI: The authors wrote this paper and used ChatGPT Pro and Gemini Deep Think only to assist with proofreading, including comments for the exposition.

Basics

As our 4-coloring algorithm in [9] is described so far, it is combinatorial and takes O(nlog⁡n)O(n\log n) time. Below we describe some of the known building blocks that we will use to get down to linear time.

Coding and tabulation. Let us recall the basic terminology about coding. A (binary) code for a set F\mathcal{F} of objects is a function c:F→{0,1}∗c:\mathcal{F}\to\{0,1\}^{*} (all finite binary words). We require that for F≠F′F\ne F', c(F)≠c(F′)c(F)\ne c(F'). Encoding of F∈FF\in\mathcal{F} is the process of creating or using the code of FF.

We shall use coding and tabulation in the following classic way. If we can code some subproblems using 12log⁡n\frac{1}{2}\log n bits on each subproblem, then we can use these bits as indices for a table/array with solutions to such subproblems. Assuming that a solution fits in an O(log⁡n)O(\log n)-bit word, we can look it up in constant time. In fact, this is the most important feature we use of the word RAM.

There are at most n\sqrt{n} indices of 12log⁡n\frac{1}{2}\log n bits, so we can spend log⁡O(1)n\log^{O(1)} n time when we first compute the solution to a subproblem, that is, when we first populate the array with solutions. This means that we have polynomial time relative to the size of the subproblem, and that is plenty for the kind of subproblems we shall consider. We shall use several different such tables, but the total space and construction time for these tables is O~(n)\widetilde{O}(\sqrt{n}) where O~\widetilde{O} hides logarithmic factors.

For our analysis, we will work with some power-of-two parameter ℓ=Θ(log⁡n)\ell=\Theta(\log n), and aim to prove that things can be coded using O(ℓ)O(\ell) bits. In the end, this means they can be coded with CℓC\ell bits for some constant CC. Choosing a power-of-two parameter ℓ\ell, such that (log⁡n)/(4C)≤ℓ≤(log⁡n)/(2C)(\log n)/(4C)\le\ell\le(\log n)/(2C), implies that we can tabulate such codes.

One of the important techniques in the coding of information is that if we know an enumeration 1,…,q1,\ldots,q of objects, e.g., vertices, then we can use an array to associate bb bits of information with each object using only bqbq bits in total. This contrasts the situation where we have to use O(log⁡q)O(\log q) bits to explain which object some information should be associated with. Here bb could be a constant, e.g., if the information is a color, but we shall use a super constant bb if the information is a counter.

Often we shall use an O(ℓ)O(\ell) bit code to code several objects each occupying a segment of the code. For these segments, we often want prefix-free coding of objects. A classic and simple way to do this is as follows. If something like the above array is encoded with bb bits, then we prefix this with an O(log⁡b)O(\log b) bit prefix-free coding of bb, e.g., a unary description of ⌈log⁡2b⌉\lceil\log_2 b\rceil consisting of ⌈log⁡2b⌉−1\lceil\log_2 b\rceil-1 0s followed by a 1, and then follow this by the binary representation of bb. With this representation, we can uniquely read the objects stored in the code, one at a time.

Divisions. The idea of rr-divisions stems from [8], but we shall use the version from the linear time construction in [13]. Below we review the relevant results from [13], but using terminology more in line with other terminology used in the current paper. We will describe the translation between the definitions in Appendix A.

A region RR of a triangulation GG is a connected subgraph of GG with at least one edge. The faces of RR are inner if they are faces of GG; otherwise they are holes. A region has only a constant number of holes.2 Note that if a region has exactly one hole, then it is a near-triangulation where the hole is the outer face. The vertices and edges around a hole are called boundary vertices and edges. Their union taken over all holes of RR forms the boundary ∂R⊆R\partial R\subseteq R.

A division of GG is a collection of regions R1,…,RkR_1,\ldots,R_k such that every face of GG is an inner face in exactly one region RiR_i. Moreover, it is required that if an edge is shared by two or more regions, then it has to be a boundary edge (that is, on a hole) of any region containing it. In fact, the converse is also true, for if an edge uvuv is on the boundary of RiR_i, then one of its incident triangles Δ\Delta in GG is in a hole of RiR_i, and Δ\Delta has to be an inner face of another region RjR_j which then also contains uvuv.

An rr-division of GG is a division with O(n/r)O(n/r) regions such that every region has at most rr vertices and at most O(r)O(\sqrt{r}) boundary vertices.

A recursive division is a rooted tree of regions such that the leaves form a division of GG and the region of any node is the union of its descending leaves. It follows that the root region is GG itself, and that any maximal anti-chain of regions in the recursive subdivision forms a division. We will also say that the children regions R1,…,RdR_1,\ldots,R_d of a region RR form a division of RR but their boundaries are still defined via GG. A face of RjR_j is inner only if it is an inner face of RR. If hh is the depth of the tree, the vertices at depth h−ih-i (0≤i≤h0 \le i \le h) are said to be on level ii in the tree.

Given an exponentially increasing sequence r⃗=(r0,…,rh)\vec{r}=(r_0,\ldots,r_h) with rh≥∣G∣r_h \ge|G|, a recursive r⃗\vec{r}-division of GG is a recursive division where all leaves are at level 0 and where the regions at level ii form an rir_i-division of GG. Moreover, regions on level ii have O(ri/ri−1)O(r_i/r_{i-1}) children on level i−1i-1.

Theorem 8 [13] Let GG be a planar graph. If r0≥sr_0 \ge s, where ss is a sufficiently large constant, and (r0,…,rh)(r_0,\ldots,r_h) is an exponentially increasing sequence with rh≥∣G∣r_h \ge|G|, then we can construct a recursive r⃗\vec{r}-division of GG in linear time.

Below we choose ss to be a sufficiently large power of 2 and define ri=s2ir_i = s2^i.

For any region RR, we define an inner face of ∂R\partial R to be a face of ∂R\partial R that is not a hole of RR. All of R∖∂RR \setminus\partial R is thus embedded in the inner faces of ∂R\partial R.

Coding the recursive r⃗\vec{r}-division

We will now show how to efficiently encode the above recursive subdivision in a way that will be useful for a linear-time 4-coloring algorithm.

Recursively encoding a planar graph with a linear number of bits A plane graph GG of order nn can be trivially encoded with O(nlog⁡n)O(n \log n) bits, using O(log⁡n)O(\log n)-bit labels for the vertices. It is also known [21] that we can get down to O(n)O(n) bits with an efficient coding as in [10]. We will now show that we can use the recursive subdivision R\mathcal{R} of Theorem 8 to derive an O(n)O(n)-bit representation of GG. This encoding is fairly standard, but the way we do it will be useful for understanding later encodings. The encoding will also allow us to encode O(1)O(1) bits of extra information with each vertex and edge.

We assume that the recursive subdivision R\mathcal{R} is ordered in the sense that the children of each region appear in some order. The coding will be generated in a depth-first traversal of R\mathcal{R} visiting children respecting the ordering. The encoding of a region RR, including the recursive coding of its descendants, will form a consecutive segment of the entire code for GG.

When we encode a region RR, we are given labels for the boundary vertices in ∂R\partial R. We will then produce a coding of RR prefixed by the length of the code for RR. The encoding should include the given labels of the boundary vertices so that they can be identified in the encoding.

Consider a level-ii region R∈RR \in\mathcal{R}. It has O(ri)O(\sqrt{r_i}) boundary vertices with given O(log⁡ri)O(\log r_i)-bit labels. The region RR has children R1,…,RdR_1,\ldots,R_d where d=O(ri/ri−1)=O(1)d=O(r_i/r_{i-1})=O(1). Let B=⋃j=1d∂Rj⊇∂RB=\bigcup_{j=1}^{d}\partial R_j \supseteq\partial R be the graph consisting of the boundary vertices and edges of these child regions. Then BB is a plane graph of size O(ri)O(\sqrt{r_i}). We make a local labeling of the vertices of BB using labels 1,…,∣V(B)∣1,\ldots,|V(B)|. We want to encode the plane graph BB by including these local labels plus a mapping from the given boundary labels in ∂R\partial R to the new labels in B=⋃j=1d∂RjB=\bigcup_{j=1}^{d}\partial R_j. We can easily do this using O(rilog⁡ri)O(\sqrt{r_i}\log r_i) bits. The encoding for the child region RjR_j is given our new labels on BB for its boundary vertices in ∂Rj⊆B\partial R_j \subseteq B.

When we decode our encoding top-down, we will already have embedded ∂R\partial R including the given labeling of its vertices. Since we can identify these vertices in BB, we can add BB to the embedding, placing B∖∂RB \setminus\partial R in the inner faces of ∂R\partial R. This includes our new local labeling of all vertices in BB, which is used recursively as input for the decoding and embedding of the child regions R1,…,RdR_1,\ldots,R_d.

At level 0, a region has constant size, and we encode it explicitly, respecting its boundary labels, using O(1)O(1) bits.

The reason this is efficient is that on level ii in the recursive r⃗\vec{r}-division, we only have O(n/ri)O(n/r_i) regions, so the space used to get from level ii to level i−1i-1 is O((n/ri)rilog⁡ri)=O(n(log⁡ri)/ri)O((n/r_i)\sqrt{r_i}\log r_i)=O(n(\log r_i)/\sqrt{r_i}) bits. The total space over all levels is thus O(n)O(n) bits. The encoding takes linear time given the recursive division which is constructed in O(n)O(n) time in [13].

Our encoding describes both GG and the ordered recursive division R\mathcal{R}. From the ordering, we get an ordering of the edges; namely, the order of first appearance of edges in the terminal region encodings. We can also use this to order the vertices based on their first occurrence in the edge ordering. These orderings imply enumerations of the vertices and edges, so we can use arrays to associate a constant amount of information with each vertex and edge, using only O(n)O(n) bits in total.

More efficient encoding of boundaries We will now improve the coding of boundaries. A region RR on level ii has O(ri)O(\sqrt{r_i}) boundary vertices, including the boundary vertices of its children. Above we encoded it with O(rilog⁡ri)O(\sqrt{r_i}\log r_i) bits using O(log⁡ri)O(\log r_i) bit labels for the boundary vertices. The main reason for the labels is that in order to decode the code, we need to know where each externally labeled boundary vertex from ∂R\partial R is placed in the graph representing RR. We will now get down to O(ri)O(\sqrt{r_i}) bits exploiting that a region RR has only a constant number of holes.

Suppose we have a plane graph WW whose edges are the edges on the boundary of a hole plus an oriented start edge uvuv, oriented following the clockwise walk around the hole. We will then follow the clockwise walk around the hole if we always turn right, that is, edge xyxy is followed by edge yzyz where zz is the neighbor of yy in WW that follows xx anti-clockwise. An important point in the description of the above boundary walk is that given the oriented edge uvuv, we do not need any further description of the hole, since the walk defines the hole.

Now consider a region RR with h=O(1)h=O(1) holes with boundaries W1,…,WhW_1,\ldots,W_h. Then ∂R=⋃k=1hWk\partial R=\bigcup_{k=1}^{h}W_k. To represent the above hole walks, we just need to store for each edge in ∂R\partial R which boundary WkW_k it belongs to, and whether it is the start edge ukvku_kv_k and, if so, with what orientation. We call this information the hole information associated with each edge of ∂R\partial R, and note that it takes only a constant number of bits per edge. We will have such hole information in mind for the boundary of every region RR in our recursive subdivision. With the above information, we also have a unique enumeration of the vertices and edges in ∂R\partial R: we do the walks of W1,…,WhW_1,\ldots,W_h, one at a time, and enumerate the vertices and edges as they are encountered for the first time in these walks.

Recall that our recursive issue is to identify the vertices in the boundary of a region among the boundaries of its children. We are given a region R0R_0 with O(1)O(1) children R1,…,RdR_1,\ldots,R_d, and our goal is to encode all their boundaries in such a way that we can identify boundary vertices of the parent region R0R_0 among the boundary vertices of the children R1,…,RdR_1,\ldots,R_d. We shall refer to this as the boundary structure ∂(R0;R1,…,Rd)\partial(R_0;R_1,\ldots,R_d).

First we encode the plane graph B=⋃j=0d∂RjB=\bigcup_{j=0}^{d}\partial R_j, which we note includes ∂R0\partial R_0. We want to apply the previous encoding of any 2-connected triangulation in linear time using a linear number of bits. To apply this to BB we add a linear number of auxiliary edges, so as to create a 2-connected triangulation B△B^\triangle. We now get the encoding of B△B^\triangle including our ordered recursive division, which also defines a linear order of the edges; namely, the first time they are encountered in terminal-region encoding in the ordered depth-first traversal. Using the linear order of the edges, we can use an array to store a constant number of bits with each edge.

For each edge in B△B^\triangle, we store if it is an auxiliary edge. If not, for j=0,…,dj=0,\ldots,d, we store if it belongs to ∂Rj\partial R_j and if so, its hole information in ∂Rj\partial R_j. All this adds up to a constant number of bits per edge, as desired. We can thus store the whole boundary structure of a region on level ii using only O(ri)O(\sqrt{r_i}) bits.

To clarify the parent-child relation, note that the boundary of each region RR will appear twice in the above boundary structures, once as a child, and once as a parent. In each of these boundary structures, we know the edges of ∂R\partial R, including the associated hole information, and this provides a complete map between the hole walks of RR in the two boundary structures.

Note that the above does not give us a more efficient encoding of the planar graphs, but it does give us a tight encoding of the relation between a parent R0R_0 and its children R1,…,RdR_1,\ldots,R_d. We shall sometimes use this boundary structure coding when ⋃j=0d∂Rj\bigcup_{j=0}^{d}\partial R_j is contained inside a larger planar graph HH.

Lemma 9 For a region R0R_0 with children R1,…,RdR_1,\ldots,R_d, suppose we have a plane graph HH containing ⋃j=0d∂Rj\bigcup_{j=0}^{d}\partial R_j. Then we can encode HH using O(∣H∣)O(|H|) bits so that, for each j=0,…,dj=0,\ldots,d, we can identify the hole walks of RjR_j in HH.

Proof Add auxiliary edges to triangulate HH and make it 2-connected, and use the linear-bit encoding above. The edge order lets us store a constant number of bits with every edge. These bits say whether the edge is auxiliary, to which ∂Rj\partial R_j it belongs, and the hole information for that ∂Rj\partial R_j. From this, after decoding HH, we recover every ∂Rj\partial R_j together with its enumeration. The total number of bits is O(∣H∣)O(|H|).

The point is that below we are going to augment ⋃j=0d∂Rj\bigcup_{j=0}^{d}\partial R_j with certain Kempe nodes and configuration nodes, and then we need to know how these connect to our boundary structure.

Leaf regions of logarithmic size and strictly containing our family Z′Z' of reducible configurations. We are only going to use the recursive r⃗\vec r-division down to some i0i_0 where ri0=s2i0=ℓr_{i_0}=s^{2i_0}=\ell where ℓ=Θ(log⁡n)\ell=\Theta(\log n) is the parameter to be chosen later such that, informally speaking, O(ℓ)<12log⁡nO(\ell)<\frac{1}{2}\log n.

An i0i_0 region thus has at most ℓ\ell vertices, implying that we can encode it with O(ℓ)<12log⁡nO(\ell)<\frac{1}{2}\log n bits, including a coloring of the vertices. There are at most n\sqrt n such representations, so we can afford to make tables over all these representations, e.g., we can precompute the reducible configurations inside of each such leaf-region in O(nlog⁡n)=o(n)O(\sqrt n\log n)=o(n) time.

Recall from Task 5 that we are given a family Z\mathcal{Z} of Ω(n)\Omega(n) non-touching induced D-reducible configurations, and that we have to select a subfamily Z′\mathcal{Z}' of linear size. We select

Z′={Z∈Z∣Z is strictly contained in some leaf region R, that is, Z⊆R−∂R}.\mathcal{Z}'=\{Z\in\mathcal{Z}\mid Z\text{ is strictly contained in some leaf region }R,\text{ that is, }Z\subseteq R-\partial R\}.

The total number of boundary vertices of leaf regions is O(n/log⁡n)O(n/\sqrt{\log n}). Since our Ω(n)\Omega(n) reducible configurations are non-touching and each has only a constant number of vertices, we still have Ω(n)\Omega(n) reducible configurations for which no vertex is a boundary vertex of a leaf region. These are the reducible configurations ZZ in Z′\mathcal{Z}'. If ZZ is in the region RR, then its ring vertices may intersect ∂R\partial R, but its completion Z^\widehat Z, that is ZZ completed with its ring, is still contained in RR.

Small regions with logarithmic boundaries We are going to use tabulation, not just for the leaf regions, but for the boundary structure of regions up to the level i1i_1 with ri1=Θ(ℓ2)r_{i_1}=\Theta(\ell^2). As described above, we can encode these boundary structures using O(ri1)=O(ℓ)O(\sqrt{r_{i_1}})=O(\ell) bits.

All the above encoding is done as a preprocessing, once and for all, in linear time. We shall use it to identify and perform Kempe changes in O(n/log⁡n)O(n/\log n) time.

Identifying Kempe chains

We have a graph that is 4-colored except for some uncolored reducible configurations. Since we have an enumeration of the vertices, the colors can be stored in an array with 3 bits per vertex (we use a third bit for “uncolored”).

We now want to identify all Kempe chains in GG based on given opposing color pairs {a,b}\{a,b\} and {c,d}\{c,d\} with {a,b,c,d}={1,2,3,4}\{a,b,c,d\} = \{1,2,3,4\}. We will only spend O(n/log⁡n)O(n/\log n) total time. Our first goal is to find out how Kempe chains connect the vertices in the rings of the uncolored reducible configurations.

Accounting We will get down to O(n/log⁡n)O(n/\log n) time by spending constant time on regions at levels i=i0,…,i1i = i_0,\ldots,i_1, that is, starting from the leaf regions. We have O(n/log⁡n)O(n/\log n) such regions. For i>i1i > i_1, the boundary size is O(ri)O(\sqrt{r_i}), and here we will spend O(ri)O(\sqrt{r_i}) time. For the whole level, this is O(rin/ri)=O(n/ri)O(\sqrt{r_i}n/r_i) = O(n/\sqrt{r_i}), so level i=i1+1i = i_1 + 1 dominates3 with a cost of O(n/log⁡n)O(n/\log n).

Kempe connectivity via Kempe edges From now on, we fix complementary pairs abab and cdcd of colors. The Kempe chains only involve the colored vertices. Since we have a proper coloring, there are no monochromatic edges, so the abab-Kempe chains are the abab-colored components. With the opposing color pairs given, the 4-colored part of the graph is partitioned into Kempe chains. We shall refer to the abab- and cdcd-colored edges as Kempe edges.

Our goal is to represent which vertices are connected by Kempe chains, and call two vertices Kempe connected if they belong to the same Kempe chain. To do this efficiently, we will manipulate the graph, introducing new Kempe nodes and edges, but such that the Kempe connectivity between original vertices is not changed. Since we only care about Kempe connectivity, we allow ourselves to add auxiliary Kempe edges between vertices of the same color, as long as they were already Kempe connected.

Contracting Kempe edges in faces Consider two subgraphs BB and HH of the same plane graphs, e.g., BB could be the boundary of a region RR of GG (and HH could consist of some Kempe chains). We need an operation that contracts the Kempe chains from HH in the faces of BB. The resulting graph, denoted BHKB_H^K, is a plane graph of size O(∣B∣)O(|B|) containing BB and such that any two nodes from BB are Kempe connected in B∪HB \cup H if and only if they are Kempe connected in BHKB_H^K. Figure 3 shows an example with ∂RGK\partial R_G^K for some region RR in GG.

Figure 3. The figure shows the graph ∂RGK\partial R_G^K that we get from the Kempe chains in the left figure. The blue nodes are Kempe nodes and the blue edges are Kempe edges. They represent Kempe connectivity between vertices in ∂R\partial R.

We consider one face Φ\Phi of BB at a time. First we delete all parts of HH in Φ\Phi that are not Kempe connected to BB. Next, for each appearance of a vertex vv on the boundary of Φ\Phi, having some incident edges in HH, we make a copy vΦv_\Phi inside Φ\Phi, attached to vv by a new Kempe edge vvΦvv_\Phi, called an “attachment edge”. This edge is attached to the boundary of Φ\Phi at the same appearance of vv. Moreover, we move each Kempe edge vw∈Φvw \in\Phi so it becomes a Kempe edge vΦwv_\Phi w. Note that if the same vertex vv appears multiple times along the boundary of Φ\Phi, then we make a separate copy vΦ′v'_\Phi with a separate attachment edge. Also note that if we had an edge vwvw contained in Φ\Phi and with both end-points in the boundary, then it will become an edge vΦwΦv_\Phi w_\Phi. When we are done, we have moved all original Kempe edges in Φ\Phi so that they are now embedded strictly inside Φ\Phi. Finally, we contract all Kempe edges strictly inside Φ\Phi, calling the result Kempe nodes. The new attachment edges now connect each boundary vertex of Φ\Phi with a Kempe node. The Kempe nodes and the attachment edges now provide exactly the same Kempe connections between boundary vertices of Φ\Phi (and in all BB) as did the Kempe edges from HH in Φ\Phi. Doing this operation on all faces of BB, we get the graph BHKB_H^K. Finally we argue that ∣BHK∣=O(∣B∣)|B_H^K| = O(|B|). The point is that for each vertex v∈Bv \in B, we add at most one vΦv_{\Phi} each time a boundary walk of Φ\Phi visits vv. The number of such vertices added in Φ\Phi is at most the total length of the boundary walks of Φ\Phi. Each edge bounds at most two faces, so the number of vertices added is at most twice the number of edges, which, in turn, is at most thrice the number of vertices in BB. Thus we have proved

Lemma 10 Let BHKB_H^K be the contraction of the Kempe edges from HH in the faces of BB. Then BHKB_H^K is a plane graph of size O(∣B∣)O(|B|) such that any two vertices in BB are Kempe connected in B∪HB \cup H if and only if they are Kempe connected in BHKB_H^K.

Figure 2. The figure shows parts of a 4-colored graph GG with a region RR (light gray background) and its boundary ∂R\partial R (bold edges). The black edges are those in the Kempe chains with the color pairing red-blue and green-yellow. Other edges are drawn in gray. Note that GG is supposed to be triangulated, so the drawing only includes some illustrative parts of GG. Also, the illustration does not include reducible configurations that are not colored (they do not intersect any boundaries).

Final goal For every region RR, we will compute both ∂RRK\partial R_R^K and ∂RG−E(R)K\partial R_{G-E(R)}^K (see Figure 3). Note that ∂RG−E(R)K\partial R_{G-E(R)}^K excludes all vertices strictly contained in RR since they are not (Kempe) connected to ∂R\partial R in ∂R∪(G−E(R))\partial R \cup(G - E(R)). We also note that ∂RGK=∂RRK∪∂RG−E(R)K\partial R_G^K = \partial R_R^K \cup\partial R_{G-E(R)}^K, but we compute ∂RRK\partial R_R^K and ∂RG−E(R)K\partial R_{G-E(R)}^K separately. We compute ∂RRK\partial R_R^K bottom-up, and using them, we will compute the ∂RG−E(R)K\partial R_{G-E(R)}^K top-down. Note that for a leaf region RR, we can use R∪∂RG−E(R)KR \cup\partial R_{G-E(R)}^K to find out which vertices in RR are Kempe connected in GG. In particular, if we have a reducible configuration Z∈Z′Z \in Z' strictly contained in RR, then we can see which of its ring vertices are Kempe connected, and since R∪∂RG−E(R)KR \cup\partial R_{G-E(R)}^K has size O(ℓ)O(\ell), this can be done simultaneously for all such configurations in RR with a single table look-up.

Figure 4. We produce ∂RRK\partial R^{\mathcal{K}}_{R} (left) bottom-up, and then ∂RG−E(R)K\partial R^{\mathcal{K}}_{G-E(R)} (right) top-down, and finally combine them to produce ∂RGK\partial R^{\mathcal{K}}_{G} (Figure 3).

Bottom-up processing We now first do a bottom-up processing of our recursion tree, starting from the leaf regions. For each region, we wish to compute ∂RRK\partial R^{\mathcal{K}}_{R}. Given the encoding of a leaf region RR and its coloring, we can compute ∂RRK\partial R^{\mathcal{K}}_{R} with a table look-up.

Above the leaf-level, consider a region RR with O(1)O(1) child regions R1,…,RdR_1,\ldots,R_d. From each child, we get the (encoding of the) graph ∂RRjK\partial R^{\mathcal{K}}_{R_j}. Let HH be the union of these graphs. Then

∂RRK=∂RHK where H=⋃j=1d∂RRjK=(⋃j=1d∂Rj)RK.(2)\partial R^{\mathcal{K}}_{R}=\partial R^{\mathcal{K}}_{H}\text{ where }H=\bigcup_{j=1}^{d}\partial R^{\mathcal{K}}_{R_j}=\left(\bigcup_{j=1}^{d}\partial R_j\right)^{\mathcal{K}}_{R}. \tag*{(2)}

The basic point here is that if RR is of level ii, then the above only involves d+1=O(1)d+1=O(1) boundaries of order O(ri)O(\sqrt{r_i}). For small regions RR of levels i≤i1i\le i_1, the size is at most ℓ2\ell^2, but the boundary size ∣∂R∣|\partial R| is only O(ℓ)O(\ell), so the computations can be done by table look-ups.

As we go regions RR on levels i>i1i>i_1, we compute ∂RRK\partial R^{\mathcal{K}}_{R} in time linear in the total size of the graphs involved in the bottom-up step (2), which is O(ri)O(\sqrt{r_i}). For the whole level ii, this is O(n/ri)=O(n/2i)O(n/\sqrt{r_i})=O(n/\sqrt{2^i}) time. Since this is only for i>i1i>i_1 where 2i1=Ω(log⁡2n)2^{i_1}=\Omega(\log^2 n), the total cost of the bottom-up processing is O(n/log⁡n)O(n/\log n).

Top-down processing Having computed ∂RRK\partial R^{\mathcal{K}}_{R} for all regions RR on or above leaf-level i0i_0, we now wish to compute all ∂RG−E(R)K\partial R^{\mathcal{K}}_{G-E(R)} in a top-down processing. The top-most region is GG, which has no boundary, so there is nothing to compute.

Suppose we have computed ∂RG−E(R)K\partial R^{\mathcal{K}}_{G-E(R)} for a region RR with O(1)O(1) child regions R1,…,RdR_1,\ldots,R_d. We compute (∂Rj)G−E(Rj)K(\partial R_j)^{\mathcal{K}}_{G-E(R_j)} as follows. Let B=∂R∪⋃j=1d∂RjB=\partial R\cup\bigcup_{j=1}^{d}\partial R_j. Then

\partial R_j^{\mathcal{K}}{}_{G-E(R_j)}=\partial R_j^{\mathcal{K}}_{B^{\mathcal{K}}_{G-E(R_j)}}\text{ where }B^{\mathcal{K}}_{G-E(R_j)}=B^{\mathcal{K}}_{\partial R^{\mathcal{K}}_{G-E(R)}}\cup\bigcup_{h\ne j}\partial R_h^{\mathcal{K}}. \tag*{(3)}

As for the bottom-up processing, the top-down processing is easily implemented in O(n/log⁡n)O(n/\log n) total time. As we described the final goal, when we for each leaf region RR have its coloring and ∂RG−E(R)K\partial R^{\mathcal{K}}_{G-E(R)}, then we know which of its vertices are in the same Kempe chains, and since this is all encoded in O(ℓ)O(\ell)-bits, we can get the information with table look-ups.

Enumeration of Kempe chains Consider a non-leaf region R0R_0 with child regions R1,…,RdR_1,\ldots,R_d and let B=⋃j=1d∂RjB = \bigcup_{j=1}^{d} \partial R_j, noting that ∂R0⊆B\partial R_0 \subseteq B. In our bottom-up processing, we computed the \partial R_j^{\mathcal{K}}_{R_j} for j=1,…,dj=1,\ldots,d, and afterwards, top-down we computed \partial R_0^{\mathcal{K}}_{G-E(R_0)}. Putting them together, we get

B_G^{\mathcal{K}} = \partial R_0^{\mathcal{K}}_{G-E(R_0)} \cup\bigcup_{j=1}^{d} \partial R_j^{\mathcal{K}}_{R_j}. \tag*{(4)}

With this information, which only takes O(ri)O(\sqrt{r_i}) bits, we know precisely where different Kempe chains intersect BB. We divide the Kempe chains intersecting BB into two types. Those who intersect ∂R0\partial R_0 and those who don’t. The latter type are said to stop in R0R_0. Equivalently, a Kempe chain stops in R0R_0 if and only if it is strictly contained in R0R_0 (that is, contained in R0−∂R0R_0-\partial R_0), but not strictly contained in any child of R0R_0.

Generally, if we have an enumeration order on a set of vertices UU, then it induces an enumeration order of the Kempe chains intersecting UU; namely, the order in which they are first encountered.

Recall that our boundary structure ∂(R0;R1,…,Rd)\partial(R_0;R_1,\ldots,R_d) provides unique enumeration of the vertices in BB, as well as an enumeration of the vertices in each ∂Rj\partial R_j. This then induces orderings of the intersecting Kempe chains, and all this information is implicit when we combine ∂(R0;R1,…,Rd)\partial(R_0;R_1,\ldots,R_d) with BGKB_G^{\mathcal{K}}. This is all represented in O(ri)O(\sqrt{r_i}) bits if R0R_0 is on level i≥i0i \geq i_0.

Combining this information with the corresponding information from the parent of R0R_0, we can follow how the same Kempe chains appear in the different enumeration orders.

For a leaf region RR, we identify all intersecting Kempe chains from ∂RG−E(R)K\partial R^{\mathcal{K}}_{G-E(R)} together with RR, all represented in O(ℓ)O(\ell) bits. The Kempe chains are enumerated as above. The Kempe chains strictly contained in a leaf region RR are said to stop in RR. Then every Kempe chain in GG stops in exactly one region.

Implementing Kempe changes For every region RR in our recursive subdivision, we have an enumeration of the Kempe chains stopping in RR. Suppose we are given a bit-string telling for each of these Kempe chains if they should be swapped or not, e.g., these bits could be chosen at random for a random Kempe change. We will now show how to implement these given changes in the coloring of GG.

The implementation of the Kempe changes is done top-down. Consider a region RR. We had an enumeration of the Kempe chains intersecting ∂R\partial R, and we assume that we, from the above, are given a bit string for the decisions for these Kempe chains. Now we add to this the decisions for the Kempe chains stopping in RR. If RR had children R1,…,RdR_1,\ldots,R_d, then for each child RjR_j, we need to translate from these bit-strings to a bit-string for the Kempe chains intersecting ∂Rj\partial R_j following their enumeration for RjR_j. However, we know the translation from ∂(R0;R1,…,Rd)\partial(R_0;R_1,\ldots,R_d) and BGKB_G^{\mathcal{K}} where B=⋃j=1d∂RjB=\bigcup_{j=1}^{d}\partial R_j.

If RR is on level i>i1i>i_1, then this involves O(ri)O(\sqrt{r_i}) Kempe chains, and all the information can be described using O(ri)O(\sqrt{r_i}) bits. On levels ii such that i0<i≤i1i_0<i\leq i_1, we have ri=O(ℓ)\sqrt{r_i}=O(\ell), so the translation can be done with a table look-up. On the high level, for i>i1i>i_1, the translation is trivially done in O(ri)O(\sqrt{r_i}) time.

When we get to a leaf region RR, from above, we get the bit string deciding the changes for Kempe chains intersecting ∂R\partial R, and we combine this with the bit strings for the Kempe chains strictly contained in RR. We now know exactly which vertices in RR whose colors we want to swap. Boundary vertices are in multiple leaf regions. The color array for each leaf stores a local copy of every vertex color in that leaf. During a Kempe change, all these local copies are updated. Copies of the same vertex receive the same Kempe chain decision, so their colors remain equal. They are initialized consistently during preprocessing, and their total number is O(n)O(n). All these colors are found in the color array for vertices in RR. Using a single table look-up based on RR, ∂RG−E(R)K\partial R^{\mathcal{K}}_{G-E(R)}, the Kempe chain swap vector, and the color array, we produce an updated color array that replaces the old one. All of these objects are represented in O(ℓ)O(\ell) bits, so the color copies in the leaf region are all updated in constant time.

We conclude that we can identify Kempe connections and implement changes in O(n/log⁡n)O(n/\log n) time.

4-coloring in linear expected time

We are now ready to implement the randomized approach from § 1.2. Recall that we first fixed a random color pairing, and then made a random choice whether or not to switch each Kempe chain.

For each region RR, we just need to generate a random bit string specifying the random choices for all Kempe chains stopping in RR. The total number of Kempe chains is at most nn. Assuming that we can generate a random word with log⁡n\log n bits in constant time, we generate all the bits in O(n/log⁡n)O(n/\log n) time. Having specified the random Kempe change, we can implement it as described above in O(n/log⁡n)O(n/\log n) time.

Next, we need to check which of the uncolored reducible configurations ZZ from Z′Z' have become 0-extendible so that ZZ can now be colored. Since they are all strictly contained in leaf regions, we can just check one leaf region RR at a time. It is represented with O(ℓ)O(\ell) bits, including the new coloring, so with a simple look-up, we perform this task for all the relevant configurations strictly contained in RR in constant time.

As described in § 1.2, we are done with high probability after O(log⁡n)O(\log n) iterations (and one iteration (Kempe change) takes O(n/log⁡n)O(n/\log n) time), thus spending O(n)O(n) time in total.

Deciding and performing Kempe changes deterministically

In this section, we shall derandomize the previous construction, so as to prove our main result; namely that we can 4-color deterministically in linear time. Technically, doing this derandomization efficiently is by far the most challenging part of this paper. The specific challenge is to prove the lemma below, which improves construction time of Lemma 4 from O(n)O(n) to O(n/log⁡n)O(n/\log n):

Lemma 11 Let Z1,…,ZqZ_1,\ldots,Z_q be some (not necessarily all) non-colored reducible configurations (from the family Z′Z' selected in § 2.1) in a triangulation GG that is 4-colored except for the remaining non-colored configurations in Z′Z'. The colorings of their rings are not yet 0-extendible. Suppose also that we have computed the recursive division with all the boundary structures ∂(R0;R1,…,Rd)\partial(R_0;R_1,\ldots,R_d) from above (this took linear time, but was only done once in the preprocessing). Finally, we assume that the participating configurations Z1,…,ZqZ_1,\ldots,Z_q are marked in the coded leaf representations, so that we do not need to handle them individually.

We can then, deterministically in O(n/log⁡n)O(n/\log n) time, find and execute a Kempe change that is improving for at least a fraction p=13⋅218p=\frac{1}{3\cdot2^{18}} of the rings, and also tell which rings got improved.

With Lemma 11, we can solve Task 5 in linear time as stated in Theorem 7. By Theorem 6, this implies that we can 4-color in linear time, so Lemma 11 implies Theorem 1.

The algorithmic proof of Lemma 11 follows the same steps as Lemma 4, but each step must be done logarithmically faster. Below we review the steps.

Before we decide on the Kempe change, we view all the rings as alive. Each time we make a decision about the Kempe change, we kill all rings that can no longer get an improving Kempe change.

First, we need to find a good color pairing: should color 1 be paired with 2, 3, or 4? This decides all the bicolored Kempe chains. Since every configuration is D-reducible, we know, for every ring, that one of these 3 pairings has an improving Kempe change. We choose a pairing such that at least 1/3 of the rings have an improving Kempe change, and thus remain alive.

With a color pairing a,ba,b and c,dc,d decided, we go through the abab- and cdcd-colored Kempe chain in an arbitrary order and decide for each whether or not to swap its colors. We always pick the choice that maximizes the conditional expected number of surviving rings from (1), that is,

∑Zi is still live2−ui,\sum_{Z_i\ \text{is still live}} 2^{-u_i},

where uiu_i is the number of undecided Kempe chains touching ZiZ_i.

When deciding on a Kempe change KK, we only need the sum restricted to live configurations touching KK. Deciding KK may kill many of these configurations, but for those ZiZ_i that are touched by KK but not killed, the survival probability 2−ui2^{-u_i} is doubled. Since we always have ui≤18u_i \le18, we note that the expectancy is always an integer multiple of 1/2181/2^{18}. Let us describe each step in more detail.

Finding the right color pairing For any given color pairing, we want to know for each non-colored configuration ZZ if there exists a Kempe change that is improving for ZZ; for then ZZ survives this color pairing. We want to count the number of survivors with each of the three color pairs, so we can pick one where 1/3 survives.

Recall from the definition of Z′Z' that ZZ is strictly contained in some leaf region RR, and all we need to know is how the Kempe chains partition the ring of ZZ. From the local perspective of ZZ, a Kempe change tells whether or not to swap the colors within each set of this partition, and for each of the constantly many configurations ZZ in D\mathcal{D}, we know which swaps are improving.

To find out how Kempe chains connect vertices in RR, we just have to consider R∪∂RG−E(R)KR \cup\partial R^{K}_{G-E(R)}, where ∂RG−E(R)K\partial R^{K}_{G-E(R)} is as computed as in § 2.2. We note that R∪∂RG−E(R)KR \cup\partial R^{K}_{G-E(R)} is represented in O(∣R∣)O(|R|) bits, including coloring, reducible configurations (alive before the color pairing is decided), and all Kempe connections between its vertices. We can therefore, with a single look-up, in constant time, decide how many configurations survive the given color pairing.

Thus, for each color pairing, we first identify the Kempe chains, then count the survivors for that pairing, and choose the one with the most survivors.

With the winning pairing, for each surviving configuration, we have some preferred improving swaps among the Kempe chains it touches. We keep these preferred swaps fixed throughout the following bottom-up decisions.

Bottom-up swap decisions on Kempe chains We are going to make the swap decisions on the Kempe chains in a bottom-up fashion, starting from the leaf regions. When we get to a region RR, we assume that we have already made decisions for all Kempe chains stopping below RR, so when we get to RR, we only have to make decisions for Kempe chains KK stopping in RR. However, to make the right decision on KK, we need to know about all the live configurations touching KK.

It is now important to note that we only consider reducible configurations ZZ strictly contained in leaf regions, so they cannot intersect the boundary of any region. Therefore, KK can only touch configurations strictly contained in RR.

When the decisions have been made for all the Kempe chains in the graph, we can implement them all top-down as described at the end of § 2.2.

Kempe chains strictly inside leaf regions First we consider the easy case of a leaf region RR. A Kempe chain KK stops in RR if and only if KK is strictly contained in RR. Since we only consider reducible configurations strictly within regions, KK can only touch reducible configurations strictly within RR. All the relevant information is therefore contained in R∪∂RG−E(R)K⃗R \cup\partial R^{\vec K}_{G-E(R)}, including prior decisions on Kempe chains in RR. In principle, we want to decide one such Kempe change KK at a time, but we can simulate this sequential process for all of them, just using the information from R∪∂RG−E(R)K⃗R \cup\partial R^{\vec K}_{G-E(R)}. Using a table, taking R∪∂RG−E(R)K⃗R \cup\partial R^{\vec K}_{G-E(R)} and the original coloring of RR as input, we can produce a bit vector of decisions.

However, for each of the at most ∣∂R∣|\partial R| Kempe chains intersecting ∂R\partial R, we need information about the live reducible configurations that they touch. The representation of such information is described below.

Deciding on batches of Kempe chains We will now discuss how to decide the changes for a batch K⃗=(K1,…,Kk)\vec K = (K_1,\ldots,K_k) of Kempe chains, simulating the decided changes in this order. These could be the Kempe chains stopping in a given region. The decisions depend on all the reducible configurations touched by these Kempe chains, but there could be Ω(n)\Omega(n) of these even for a single Kempe chain. We want to argue that the information needed for the decisions can be contained in O(k)O(k) counters.

We need to consider reducible configurations ZZ that touch some Kempe chains from K⃗\vec K and which are alive before we make switch decisions on K⃗\vec K. Relative to our Kempe batch K⃗\vec K, the main type of such a reducible configuration ZZ is the set of Kempe chains from K⃗\vec K that ZZ touches. We claim that the number of main types relative to K⃗\vec K is only O(k)O(k). To see this, we construct a plane graph representation K⃗c\vec K^c as follows. We contract each Kempe chain from K⃗\vec K to a Kempe node. Moreover, we contract every configuration touched by the Kempe nodes to a configuration node. We remove the rest of the graph except for the edges between the Kempe nodes and the configuration nodes, so now we have a plane bipartite graph representing all connections between Kempe chains from K⃗\vec K and the configurations they touch. Next we remove all parallel edges since we do not care how many times a given Kempe chain touches the same configuration. Finally, and this is the big reduction, we remove all but one configuration node of each main type.

We claim that the number of remaining configuration nodes is O(k)O(k). With black Kempe nodes and white configuration nodes, this follows from the following general lemma:

Lemma 12 Consider a simple plane bipartite graph where the two partite sets are black and white. Suppose that every white vertex has at least one black neighbor and no two white vertices are adjacent to the same set of black vertices (think of this as a simple plane hypergraph where the white vertices define the hyperedges). Then the number of white vertices is within a constant factor of the number of black vertices.

Proof Let qq be the number of black vertices. If q≤2q \le2, the statement is immediate since there are at most 2q2^q different sets of black neighbors. Assume q≥3q \ge3. There are at most qq white vertices of degree 1. For the white vertices of degree 2, suppress each such white vertex to an edge between its two black neighbors. Since no two white vertices have the same set of black neighbors, this gives a simple plane graph on the qq black vertices, and hence there are at most 3q−63q - 6 white vertices of degree 2.

Let uu be the number of white vertices of degree at least 3. Delete all other white vertices. The remaining graph is a simple bipartite plane graph with q+uq+u vertices and at least 3u3u edges. Hence by Euler’s formula for triangle-free planar graphs,

3u≤2(q+u)−4,3u \le2(q+u) - 4,

so u≤2q−4u \le2q - 4. Thus there are at most q+3q−6+2q−4=6q−10q + 3q - 6 + 2q - 4 = 6q - 10 nonempty sets of black neighbors. ■

There can be a linear number of configurations of each main type, but we claim that we can represent all information relevant to our decisions using only a constant number of counters for each main type. More precisely, we divide each main type into a constant number of subtypes. If a configuration ZZ touches ss different Kempe chains from K⃗\vec{K}, then the subtype tells which of these should be swapped to get the preferred improving Kempe changes for ZZ. There are 2s2^s options.

The subtype also tells the number tt of undecided Kempe chains outside K⃗\vec{K} that ZZ touches. Then s+ts+t is bounded by the ring size, which is at most 18. Therefore, the number of subtypes is at most 218+12^{18+1}.

Each configuration node in K⃗C\vec{K}^{C} represents configurations of the same main type and has counters for how many configurations each subtype represents. Recall that we only count configurations that were alive just before the swap decisions on K⃗\vec{K}.

With the above representation in place, we will now decide on the changes for our Kempe chains K1,…,KkK_1,\ldots,K_k. Before we decide on KjK_j, the expected number of surviving configurations touched by KjK_j is a sum over all types (main types with subtypes). To contribute, the main type should touch KjK_j and for the subtype, the preferred swap decisions on K1,…,Kj−1K_1,\ldots,K_{j-1} should agree with those we made. If the main type touches uu Kempe chains in Kj,…,KkK_j,\ldots,K_k, then its survival probability is 1/2u+t1/2^{u+t}, so the contribution is the counter times 1/2u+t1/2^{u+t}.

When we decide on KjK_j, we double the above probability for subtypes agreeing with the decision, and zero the probability of those that do not agree. We make a decision that maximizes the resulting total probability.

For a more efficient implementation, we can, for each subtype, maintain whether it is still alive after the decisions made so far on K⃗\vec{K}, and if so, maintain the above number u+tu+t of undecided Kempe chains it touches. Then, when we make the decision on KjK_j, we only involve the configuration types touching KjK_j. Since the number of configuration types is O(k)O(k) and each only touches O(1)O(1) Kempe chains, the total time needed to decide on K⃗\vec{K} is O(k)O(k) if we use a simple combinatorial algorithm.

Also, if we can represent K⃗C\vec{K}^{C} with all its counters in O(ℓ)O(\ell) space, then we can make all the decisions with a table look-up in constant time. However, there will be some situations where the combinatorial algorithm is too slow and where we have too much information for a table look-up.

Bottom-up construction of relevant main configuration types We will now show how to efficiently compute main configuration types for regions. For now we do not include subtypes and counters, and we will ignore if a main type represents a live configuration. Relative to a batch K⃗\vec{K} of Kempe chains, the main type of a configuration is the subset of K⃗\vec{K} that it touches. Recall that our description of K⃗C\vec{K}^{C} contracted each Kempe chain to a single Kempe node and a configuration of each main type to a configuration node. In Lemma 12, this is used to show that the number of main types is linear in the size of K⃗\vec{K}. However, for the representation of Kempe chains intersecting the boundary of RR, instead of contracting these Kempe chains completely, we will use the plane graph ∂RGK\partial R^{K}_{G} where the Kempe chains in GG intersecting ∂R\partial R are only contracted inside the faces of ∂R\partial R.

We will augment the graph ∂RGK\partial R^{K}_{G} with configuration nodes from the main types from RR relative to the Kempe chains intersecting ∂R\partial R. More precisely, we construct ∂RGRKC\partial R^{KC}_{GR} as follows. From RR, we keep an arbitrary configuration from each main type relative to the Kempe chains intersecting ∂R\partial R. No other configurations from RR are relevant. We contract each main-type configuration as we constructed K⃗C\vec{K}^{C}. If one of these configurations has more than one edge to the same Kempe chain, we delete all but one of them. Finally, we do the contractions in the faces of ∂R\partial R of the Kempe chains intersecting ∂R\partial R. What remains is ∂R\partial R with Kempe nodes and main type configuration nodes in the faces.

The number of Kempe chains intersecting ∂R\partial R is bounded by the size of ∂R\partial R, and by Lemma 12, their number also bounds the number of main configuration types since this number would be the same if we completely contracted all the Kempe chains. The number of main configuration types is thus O(∣∂R∣)O(|\partial R|) and we already know that ∂RGK\partial R^{K}_{G} has size O(∣∂R∣)O(|\partial R|), so we conclude that ∂RGRKC\partial R^{KC}_{GR} has size O(∣∂R∣)O(|\partial R|).

Our representation of ∂RGK\partial R_{G}^{\mathcal{K}} came with an enumeration of the Kempe chains intersecting ∂R\partial R, and in ∂RGRKC\partial R_{GR}^{\mathcal{KC}}, we can see the Kempe chains touched by a configuration node. We now get a natural enumeration of the main configuration types in ∂RGRKC\partial R_{GR}^{\mathcal{KC}}. For each main type of a configuration ZZ, we first sort the indices of the Kempe chains touched by ZZ. Second, we order the main types lexicographically with respect to these sorted lists. Thus we get an enumeration of all main configuration types in ∂RGRKC\partial R_{GR}^{\mathcal{KC}}.

Figure 5. The figure of ∂RGRKC\partial R_{GR}^{\mathcal{KC}}. There are three main configuration types: {K1,K2}\{K_1, K_2\}, {K1,K2,K3}\{K_1, K_2, K_3\}, {K1,K3}\{K_1, K_3\}, and each counter is 5, 1 or 2. For simplicity, subtypes are ignored in these counts.

Now we consider a region R0R_0 with child regions R1,…,RdR_1,\ldots,R_d. Our goal is to construct ∂RGR0KC\partial R_{GR_0}^{\mathcal{KC}} given ∂RGRjKC\partial R_{GR_j}^{\mathcal{KC}} for each child RjR_j. Let B=⋃j=1d∂RjB=\bigcup_{j=1}^{d}\partial R_j, and recall that ∂R0⊆B\partial R_0\subseteq B. From (4) we have

BGK=∂RG−E(R0)K∪⋃j=1d∂RGRjKB_{G}^{\mathcal{K}}=\partial R_{G-E(R_0)}^{\mathcal{K}}\cup\bigcup_{j=1}^{d}\partial R_{G R_j}^{\mathcal{K}}

When we combine BGKB_{G}^{\mathcal{K}} with the boundary structure ∂(R0;R1,…,Rd)\partial(R_0;R_1,\ldots,R_d), we have all the information needed to follow how the Kempe chains intersect the boundaries of the holes of each individual boundary ∂Rj\partial R_j, including the parent boundary ∂R0\partial R_0.

We now want to construct BGR0KCB_{GR_0}^{\mathcal{KC}} which is BGKB_{G}^{\mathcal{K}} with a configuration node from each main type in R0R_0 added. We will construct it from the ∂RGRjKC\partial R_{GR_j}^{\mathcal{KC}} that we get from the child regions RjR_j.

We want to fill all the faces Φ\Phi of BB. Either Φ\Phi is a hole of R0R_0, an empty triangle of GG, or an inner face of some ∂Rj\partial R_j. If Φ\Phi is a hole of R0R_0, then Φ\Phi is outside R0R_0 and then we just copy in the Kempe nodes from ∂RG−E(R0)K\partial R_{G-E(R_0)}^{\mathcal{K}}. If Φ\Phi is an inner face of some ∂Rj\partial R_j, we simply copy the configuration of Kempe nodes and main type configuration nodes from this face in ∂RGRjKC\partial R_{GR_j}^{\mathcal{KC}}. As a final cleaning step, note that we, from different RjR_j, may have configurations of the same main type. In this case, we delete all but one of them.

From BGR0KCB_{GR_0}^{\mathcal{KC}}, we can easily construct ∂RGR0KC\partial R_{GR_0}^{\mathcal{KC}} and K⃗C\vec{K}^{\mathcal{C}}, where K⃗\vec{K} consists of the Kempe chains stopping in R0R_0. To get ∂RGR0KC\partial R_{GR_0}^{\mathcal{KC}} we essentially just delete all Kempe chains in K⃗\vec{K} from BGR0KCB_{GR_0}^{\mathcal{KC}} since these are exactly the Kempe chains that do not intersect ∂R0\partial R_0. Next, inside each inner face of ∂R0\partial R_0, we contract the remaining Kempe components to single Kempe nodes. Finally, since we have removed the Kempe chains from K⃗\vec{K}, the configuration nodes may now be incident to fewer Kempe chains, and it is the incident Kempe chains that define the type. The types thus get reduced, and several of the previous types may get reduced to the same type. However, we keep only one configuration node of each type, and we delete types that become empty in the sense of not being incident to any remaining Kempe chain. The construction of K⃗KC\vec{K}^{KC} is similar, but this time, remove the Kempe chains from BGR0KCB_{GR_{0}}^{KC} that are not in K⃗\vec{K}.

We let ∂(R0;R1,…,Rd)GRKC\partial(R_{0};R_{1},\ldots,R_{d})_{GR}^{KC} denote the combination of all the above information. It provides us ∂Rj,GRjKC\partial R_{j,GR_{j}}^{KC} for j=0,…,dj=0,\ldots,d, and it tells us how to translate between the enumerations of Kempe chains and main configuration types in the different ∂Rj,GRjKC\partial R_{j,GR_{j}}^{KC}, as well as for K⃗c\vec{K}^{c}.

In the following bounds for the combined structure, let ii be the level of R0R_{0}; the total size of the parent and child boundaries is O(ri)O(\sqrt{r_i}). Note that all the above information in ∂(R0;R1,…,Rd)GRKC\partial(R_{0};R_{1},\ldots,R_{d})_{GR}^{KC} is coded in planar graphs of total size O(ri)O(\sqrt{r_i}), hence represented with O(ri)O(\sqrt{r_i}) bits. We claim that we can also compute ∂(R0;R1,…,Rd)GRKC\partial(R_{0};R_{1},\ldots,R_{d})_{GR}^{KC} in O(ri)O(\sqrt{r_i}) time. The only slightly non-trivial issues are sorting the main types. Normally sorting takes super-linear time, but not in our case. Recall that the main type of a configuration ZZ is represented as the sorted list of some of the Kempe chains from ∂(R0;R1,…,Rd)GKC\partial(R_{0};R_{1},\ldots,R_{d})_{G}^{KC} that are touched by ZZ. These Kempe chains are indexed within ∂(R0;R1,…,Rd)GKC\partial(R_{0};R_{1},\ldots,R_{d})_{G}^{KC}, so all relevant indices are O(ri)O(\sqrt{r_i}). The list has constant length because ZZ can only touch a constant number of Kempe chains (indeed at most 18), so sorting the index list is trivially done in constant time. The total number of main types nodes in the input is O(ri)O(\sqrt{r_i}). We can therefore sort the main types lexicographically in O(ri)O(\sqrt{r_i}) time using the classic Radix Sort. We do this sorting when we want to enumerate and index the main types. We also use it when we want to identify nodes of the same type in order to remove duplicates. Thus we can compute ∂(R0;R1,…,Rd)GRKC\partial(R_{0};R_{1},\ldots,R_{d})_{GR}^{KC} in O(ri)O(\sqrt{r_i}) time. As usual, we note that if ri=O(ℓ)\sqrt{r_i}=O(\ell), then we can compute everything in constant time with a table look-up. This, however, does not include counters and sub-types.

Involving subtypes and counters We will now describe combinatorially how to deal with subtypes and counters. We are again considering a region R0R_{0} with children R1,…,RdR_{1},\ldots,R_{d}. Inductively, what we get from each RjR_{j} is ∂Rj,GRjKC\partial R_{j,GR_{j}}^{KC}, which has a configuration node of each main type relative to the Kempe chains intersecting ∂Rj\partial R_{j}. Such a configuration node TT represents all live configurations ZZ touching the same subset of these Kempe chains. When we say that ZZ is live, we mean that its preferred improving change agrees with all the swap decisions made for Kempe chains stopping below RjR_{j}. The live configurations represented by TT are divided into constantly many subtypes based on their preferred improving swap decisions for the constantly many Kempe chains that they touch and which intersect ∂Rj\partial R_{j}. These are the only undecided Kempe chains that they touch. If TT represents no live configurations, it should have been deleted. For each subtype, we have a counter for how many live configurations it represents. Our enumeration of main types in ∂Rj,GRjKC\partial R_{j,GR_{j}}^{KC} can be easily extended to the subtypes, and then the counters are all contained in an array AjA_{j}. We get such an array AjA_{j} from each child RjR_{j}, and in the recursive step we fill out A0A_{0} for R0R_{0}.

With B=⋃j=1d∂RjB=\bigcup_{j=1}^{d}\partial R_{j}, we will now construct BGR0KCB_{GR_{0}}^{KC}, this time including subtypes with counters. Several child structures ∂Rj,GRjKC\partial R_{j,GR_{j}}^{KC} could have the same main type, that is, live configurations touching the same set of undecided Kempe chains. When we delete duplicates, we just add up the counters for the subtypes.

Next we want to construct K⃗C\vec{K}^{C} where K⃗\vec{K} are the Kempe chains stopping in R0R_{0}. Each main type TT from ∂Rj,GRjKC\partial R_{j,GR_{j}}^{KC} touched a subset of the Kempe chains intersecting ∂Rj,GRjKC\partial R_{j,GR_{j}}^{KC}. From this set, we get a reduced type T′T' that removes all Kempe chains not in K⃗\vec{K}, so the reduced type only tells which Kempe chains from K⃗\vec{K} it touches.

Now consider the subtypes of TT. They are determined by the preferred swap decisions for all Kempe chains intersecting ∂Rj\partial R_{j} that they touch. They only need preferred swap decisions for the Kempe chains from K⃗\vec{K} that they touch. However, the subtype also counts the number uu of undecided Kempe chains touched by

Look-upAdditional inputIterations
Construct K⃗[h]C\vec{K}[h]^CThe segment K⃗[h]\vec{K}[h]O(q)O(q)
Update B[h]B[h]K⃗[h]C\vec{K}[h]^C, SS, Aj[g]A_j[g], and current B[h]B[h]O(q2)O(q^2)
Decide swaps for K⃗[h]\vec{K}[h]K⃗[h]C\vec{K}[h]^C and populated B[h]B[h]O(q)O(q)
Update A0[h]A_0[h]Completed SS, Aj[g]A_j[g], and current A0[h]A_0[h]O(q2)O(q^2)

caption: The table summarizes the look-up steps in the order they are done for the processing of the region R0R_0. Whenever required, the input also contains ∂(R0;R1,…,Rd)GRKC\partial(R_0; R_1, \ldots, R_d)_{G_R}^{KC}, the relevant segment indices and lengths, the counter width, and the length of the decided prefix in SS. All these inputs, together with any one source array segment and one target array segment, occupy O(ℓ)O(\ell) bits.

:::

the configuration that intersect ∂Rj\partial R_j and are not in K⃗\vec{K}.

We now have all the counters needed to make the swap decisions for the Kempe chains in K⃗\vec{K}, and we record these decisions.

The next step is to remove Kempe chains in K⃗\vec{K} from BGR0KCB_{G_{R_0}}^{KC}. First we have to remove all subtypes not agreeing with the decisions we just made on K⃗\vec{K}. The remaining subtypes are only distinguished by the decisions on Kempe chains touching ∂R0\partial R_0, and then we can construct ∂R0GR0KC\partial R_0{}_{G_{R_0}}^{KC} as described earlier, once again just adding up counters for subtypes when duplicates are removed. The counters for all types are contained in an array A0A_0, completing the recursive step.

Even including counters of subtypes, a simple algorithm can do the above processing of R0R_0 in time O(ri)O(\sqrt{r_i}). As usual, this suffices if R0R_0 is on level ii with ri=Ω((log⁡n)2)r_i = \Omega((\log n)^2).

However, with counters, we must process more information. If R0R_0 is a region on level ii, then the counters for subtypes may need log⁡ri\log r_i bits, so the total space is O(rilog⁡ri)O(\sqrt{r_i}\log r_i), and if this is ω(ℓ)\omega(\ell), then we cannot do the processing just using a look-up table. This means that we can only use simple table look-ups for ri=O((log⁡n)2/(log⁡log⁡n)2)r_i = O((\log n)^2/(\log\log n)^2). Below, we handle the remaining cases.

Transferring counters.

We will now show how to handle regions on level ii where

(log⁡n)2(log⁡log⁡n)2<ri<(log⁡n)2.\frac{(\log n)^2}{(\log\log n)^2} < r_i < (\log n)^2.

Let qq be an integer such that qℓ=Θ(rilog⁡ri)q\ell= \Theta(\sqrt{r_i}\log r_i). Then q=O(log⁡log⁡n)q = O(\log\log n) is the factor by which the information including counters is too large for a single table look-up.

However, we will show how to handle this case in O(q2)O(q^2) time. There are O(n(log⁡log⁡n)2/(log⁡n)2)O(n(\log\log n)^2/(\log n)^2) such regions, so the total time for all these regions becomes O(n(log⁡log⁡n)4/(log⁡n)2)=o(n/(log⁡n))O(n(\log\log n)^4/(\log n)^2) = o(n/(\log n)), which is fine for the proof of Lemma 11.

The construction below is elementary, but this is only because we have been very careful above to make sure that we have a compact understanding of the connection between different enumerations of types.

We now consider a region R0R_0 on level ii with children R1,…,RdR_1,\ldots,R_d. Together with each child RjR_j, we have ∂RjGRjKC\partial R_j{}_{G_{R_j}}^{KC} in O(ℓ)O(\ell) bits plus the array AjA_j of counters for all types in ∂RjGRjKC\partial R_j{}_{G_{R_j}}^{KC}. The total processing of R0R_0 is summarized in Table 1.

Let K⃗\vec{K} be Kempe chains stopping in R0R_0. We already know how to compute K⃗C\vec{K}^{C} with a single table look-up, and this includes all the main types relative to K⃗\vec{K}. However, to make the swap decisions for K⃗\vec{K}, we need all the subtype counters from A1,…,AdA_1,\ldots,A_d.

The simple idea now is that we partition K⃗\vec{K} into qq segments K⃗[h]\vec{K}[h] each with ℓ−=O(ri/q)\ell^{-}=O(\sqrt{r_i}/q) Kempe chains, and make the swap decisions for one segment K⃗[h]\vec{K}[h] at a time. The point here is that an array of O(ℓ−)O(\ell^{-}) counters, each with O(log⁡ri)O(\log r_i) bits, fits in O(ℓ)O(\ell) bits, and this can be used for a table look-up. As we proceed, we add the decisions to one swap decision vector SS for all of K⃗\vec{K}. The vector SS is stored in O(ℓ)O(\ell) bits.

To make the decisions for K⃗[h]\vec{K}[h], we first construct K⃗[h]C\vec{K}[h]^{C} describing the configuration types relevant to K⃗[h]\vec{K}[h]. By Lemma 12, there are only O(∣K⃗[h]∣)=O(ℓ−)O(|\vec{K}[h]|)=O(\ell^{-}) main types, and only a constant factor more subtypes. We will populate a corresponding counter array B[h]B[h], noting that it only needs O(ℓ)O(\ell) bits. When B[h]B[h] has been populated, we can make the swap decisions for K⃗[h]\vec{K}[h] using a single table look-up.

From ∂(R0;R1,…,Rd)GRKC\partial(R_0;R_1,\ldots,R_d)^{KC}_{GR} and K⃗[h]C\vec{K}[h]^{C}, we have all the information we need to map type indices from the AjA_j to type indices from B[h]B[h]. Combining this with the vector SS of prior swap decisions for K⃗[1..h−1]\vec{K}[1..h-1], we also know which subtypes should be eliminated because they did not agree with the prior decision.

We now also divide AjA_j into qq segments of ℓ−\ell^{-} counters. One such segment Aj[g]A_j[g] is stored in O(ℓ)O(\ell) bits. If we combine this with B[h]B[h], ∂(R0;R1,…,Rd)GRKC\partial(R_0;R_1,\ldots,R_d)^{KC}_{GR}, K⃗[h]C\vec{K}[h]^{C}, and SS, then we know how to update B[h]B[h] with the counters from Aj[g]A_j[g]. This is only O(ℓ)O(\ell) bits of information, so we can compute B[h]B[h] updated with Aj[g]A_j[g] using a single look-up.

We have to update B[h]B[h] using the counters from all segments in all AjA_j, but there are only O(q)O(q) such segments in total, so we need only O(q)O(q) table look-ups. When done populating B[h]B[h], we make the swap decisions for K⃗[h]\vec{K}[h] as described above using a single table look-up.

We have to repeat this for each of the qq segments K⃗[g]\vec{K}[g] of Kempe chains stopping in R0R_0. The total number of table look-ups to compute all swap decisions for K⃗\vec{K} is therefore O(q2)O(q^2), as claimed.

Next, to complete the recursive step, we need to compute the array A0A_0 of subtype counters for ∂R0GR0KC\partial R_0{}_{GR_0}^{KC}. We use the exact same idea as above, dividing A0A_0 into segments A0[h]A_0[h]. Using A0[h]A_0[h], Aj[g]A_j[g], ∂(R0;R1,…,Rd)GRKC\partial(R_0;R_1,\ldots,R_d)^{KC}_{GR}, and SS, we know to update A0[h]A_0[h] with Aj[g]A_j[g], and we can again do this with a single table look-up. The total number of segment pairs considered is O(q2)O(q^2). We conclude that we can complete the recursive step for R0R_0 in O(q2)O(q^2) time, as claimed.

This completes the proof of Lemma 11, hence of Theorem 7 and Theorem 1.

Our notion of divisions versus those in [13]

In this appendix, we describe how to translate between our notion of rr-divisions and those in [13]. Our presentation assumes that the reader is familiar with [13] so that we only have to focus on the differences.

Difference in definitions Our definition of divisions is a bit cleaner and stricter than the one in [13], but is satisfied by the construction in [13].

In both papers, a division of GG is a collection of regions R1,…,RkR_1,\ldots,R_k. In this paper, we require that every face of GG is an inner face of exactly one region RiR_i.

In [13] they only require that every edge in GG is in at least one region. They say a boundary edge [13] is any edge that is shared by multiple regions. Like us, they further require that such shared edges are on holes in any region they belong to. However, with their definition, an edge on a hole in a region might not be a boundary edge. An example could be a division into three regions meeting in the sides of an inner triangle Δ\Delta of GG. If none of them contain Δ\Delta, then they each have a side of Δ\Delta on a hole, but these sides are not shared, so according to [13] they are not boundary edges. With our requirements to divisions, the above situation cannot happen because some region would have to contain Δ\Delta. As noted in § 2, with our requirements for divisions, an edge uvuv is on a hole of RiR_i (our definition of a boundary edge) if and only if uvuv is shared with another region RjR_j (the definition of a boundary edge in [13]).

The construction from [13] implies that a vertex shared by regions is incident to a shared edge, so, for edges, a vertex is on a hole of a region if and only if it is shared by another region.

A nice feature of defining boundary vertices and edges as those on a hole of a region is that we only need to know a region RR to know its boundary ∂R\partial R. We do not need to know anything about other regions of a division.

The construction of divisions is the same (almost) We now consider the recursive bi-division in [13 §3].

Starting from a region RR, in step 7, they find a simple-cycle separator CC. This is a simple cycle in the graph G′G' where they have placed a star in each hole of GG. This means the cycle follows edges of GG and can cross a hole via the star, but because it is simple, it can cross any given hole at most once.

The cycle partitions the plane, and we have two closed discs Φ0=Int⁡(C)\Phi_0=\operatorname{Int}(C) and Φ1=Ext⁡(C)\Phi_1=\operatorname{Ext}(C). For i=0,1i=0,1, we have a child region RiR_i consisting of all parts of RR contained in Φi\Phi_i. In particular, this implies that we get a bipartition of the inner faces of RR. Inductively, it follows that if we start from R=GR=G where all faces of RR are inner, then the recursive division will partition the inner faces between the resulting regions.

In [13], they call our inner faces natural faces, and they do indeed point out that the bi-division bi-partitions these faces. However, they make a minor mistake in their definition of the child regions RiR_i. They only include edges on the sides of the inner faces or in C∩RC\cap R, but as we can see in their Figure 1 (d), we can get edges with holes on both sides, and if RR had such an edge uvuv that is not in CC, then [13] would not pass uvuv down to any of its children. This could lead to disconnected regions contradicting their unproven Lemma 4, and it also leads to a contradiction of their Definition 7. Here we include those forgotten edges in R0R_0 and R1R_1 by giving them all parts of RR contained in Φ0\Phi_0 and Φ1\Phi_1, respectively.

Bound on the number of children A final difference is that we state that regions on level ii have O(ri/ri−1)O(r_i/r_{i-1}) children on level i−1i-1. This bound is not in [13], but it follows by a modification of their proof in [13 §3.3] that their rr-division has only O(N/r)O(N/r) regions where N=∣V∣N=|V| (while modifying their proof, we also had to fix a gap in their argument, see discussion above Lemma 13 below). Their recursive subdivision is topologically embedded in a binary recursive subdivision represented by a binary tree TT. Each node x∈Tx\in T represents a region R(x)R(x). Let n(x)=∣R(x)∣n(x)=|R(x)| and b(x)=∣∂R(x)∣b(x)=|\partial R(x)|. For r<n(x)r<n(x), let Sr(x)S_r(x) be the set of the highest descendants yy of xx such that n(y)≤rn(y)\le r (possibly y=xy=x). The regions represented by Sr(x)S_r(x) form a division, but not yet an rr-division. Next let Sr′(y)S'_r(y) be the set of the highest descendants zz of yy such that b(z)≤c′rb(z)\le c'\sqrt{r} for some constant c′c'. Finally define Sr∗(x)=⋃{Sr′(y)∣y∈Sr(x)}S^*_r(x)=\bigcup\{S'_r(y)\mid y\in S_r(x)\}. Relating back to our levels, if R(x)R(x) is a region on level ii then its child regions on level i−1i-1 form the set Sri−1∗(x)S^{*}_{r_{i-1}}(x). Moreover, by definition of level ii, n(x)≤rin(x) \le r_i and b(x)=O(ri)b(x) = O(\sqrt{r_i}).

For general x∈Tx \in T and r≤n(x)r \le n(x), we will argue that ∣Sr∗(x)∣=O(n(x)/r+b(x)/r)|S^{*}_r(x)| = O(n(x)/r + b(x)/\sqrt{r}). In [13 §3.3] they argue that if xx is on depth 0 (mod 3) in TT, then ∑y∈Sr(x)b(y)≤b(x)+O(n(x)/r)\sum_{y \in S_r(x)} b(y) \le b(x) + O(n(x)/\sqrt{r}). Working on those depths is all they need in [13 §3.3], but the same holds for arbitrary depths since the binary subdivision uses separator cycles of size at most O(n(x))=O(n(x)/r)O(\sqrt{n(x)}) = O(n(x)/\sqrt{r}).

Next we want to argue that ∣Sr(x)∣=O((n(x)+b(x))/r)|S_r(x)| = O((n(x) + b(x))/r). In [13], they argue this (for the special case where xx is the root with b(x)=0b(x) = 0) by referring to the parents of yy of z∈Sr(x)z \in S_r(x), since they have n(y)>rn(y) > r. However, these parents can overlap a lot, e.g., yy could have another child y′y' containing almost all of yy, and with a child z′∈Sr(x)z' \in S_r(x). We therefore present a different proof that fixes this issue in [13].

Lemma 13 ∣Sr(x)∣=O((n(x)+b(x))/r)|S_r(x)| = O((n(x) + b(x))/r).

Proof We want to argue that a constant fraction of the nodes z∈Sr(x)z \in S_r(x) have n(z)>r/2n(z) > r/2.

Consider any node y∈Ty \in T with children y0y_0 and y1y_1. We assume n(y)n(y) is bigger than some large enough constant. From the construction in [13], we have some simple inequalities. Since R(y0)R(y_0) and R(y1)R(y_1) divide R(y)R(y) with some overlap, we have n(yi)≤n(y)n(y_i) \le n(y) and n(y0)+n(y1)>n(y)n(y_0) + n(y_1) > n(y). Moreover, if yy is at depth 0 mod 3 in TT, then by [13 (2)],

max⁡{n(y0),n(y1)}≤0.75n(y)+O(n(y))<0.8n(y).(5)\max\{n(y_0), n(y_1)\} \le0.75n(y) + O(\sqrt{n(y)}) < 0.8n(y). \tag*{(5)}

This also implies

min⁡{n(y0),n(y1)}>0.2n(y).(6)\min\{n(y_0), n(y_1)\} > 0.2n(y). \tag*{(6)}

Now consider the subtree T′T' of TT rooted in xx and containing all nodes yy with n(y)>rn(y) > r. The parents of nodes z∈Sr(x)z \in S_r(x) are exactly the nodes in T′T' with fewer than two children. Also, ∣Sr(x)∣≤2∣T′∣|S_r(x)| \le2|T'|. Moreover, if yy is a leaf in T′T', then it has at least one child z∈Sr(x)z \in S_r(x) with n(z)>r/2n(z) > r/2.

We need to argue that the size of T′T' is linear in the number of leaves. To do that, we will bound the maximal length of a path of single-child-nodes in T′T'.

Every third node yy on such a path is at depth 0 mod 3, and if n(y)≥5rn(y) \ge5r, then by (6), the children have n(yi)>0.2n(y)≥rn(y_i) > 0.2n(y) \ge r, so both children are in T′T', that is, yy is a branching node.

However, if n(y)<5rn(y) < 5r and yy is at depth 0 mod 3, then, by (5), both children have n(yi)≤0.8n(y)n(y_i) \le0.8n(y). This means that after passing at most 8 such nodes, all children have n(yi)≤rn(y_i) \le r, implying that they are not in T′T', i.e., that we have reached a leaf. We conclude that the maximal single-child-path in T′T' is of length 24, hence that the total number of nodes in T′T' is linear in the number of leaves. This completes the proof that a constant fraction of the nodes z∈Sr(x)z \in S_r(x) have n(z)>r/2n(z) > r/2.

Since only boundary vertices are shared in the division represented by Sr(x)S_r(x), we know that

∑z∈Sr(x)n(z)≤n(x)+∑z∈Sr(x)b(z)≤n(x)+b(x)+O(n(x)/r)=O(n(x)+b(x)).\sum_{z \in S_r(x)} n(z) \le n(x) + \sum_{z \in S_r(x)} b(z) \le n(x) + b(x) + O(n(x)/\sqrt{r}) = O(n(x) + b(x)).

Since a constant fraction of the nodes z∈Sr(x)z \in S_r(x) have n(z)>r/2n(z) > r/2, we conclude that ∣Sr(x)∣=O((n(x)+b(x))/r)|S_r(x)| = O((n(x) + b(x))/r).

By [13 (13)], for every y∈Sr(x)y \in S_r(x), we have ∣Sr′(y)∣=O(1+b(y)/r)|S'_r(y)| = O(1 + b(y)/\sqrt{r}), so we conclude that

∣Sr∗(x)∣=∑y∈Sr(x)∣Sr′(y)∣=O(∣Sr(x)∣+b(x)+O(n(x)/r)r)=O(n(x)/r+b(x)/r).|S^{*}_r(x)| = \sum_{y \in S_r(x)} |S'_r(y)| = O\left(|S_r(x)| + \frac{b(x) + O(n(x)/\sqrt{r})}{\sqrt{r}}\right) = O(n(x)/r + b(x)/\sqrt{r}).

Finally, we insert n(x)≤rin(x) \le r_i, b(x)=O(ri)b(x) = O(\sqrt{r_i}), and r=ri−1r = r_{i-1}, and get ∣Sri−1∗(x)∣=O(ri/ri−1+ri/ri−1)=O(ri/ri−1)|S^*_{r_{i-1}}(x)| = O(r_i/r_{i-1} + \sqrt{r_i}/\sqrt{r_{i-1}}) = O(r_i/r_{i-1}).

References

  1. [1]F. Allaire and E. R. Swart. A systematic approach to the determination of reducible configurations in the four-color conjecture. J. Combin. Theory Ser. B, 25(3):339–362, 1978.
  2. [2]K. Appel and W. Haken. Every planar map is four colorable. I. Discharging. Illinois J. Math., 21(3):429–490, 1977.DOI
  3. [3]K. Appel and W. Haken. Every planar map is four colorable, volume 98 of Contemporary Mathematics. American Mathematical Society, Providence, RI, 1989. With the collaboration of J. Koch.
  4. [4]K. Appel, W. Haken, and J. Koch. Every planar map is four colorable. II. Reducibility. Illinois J. Math., 21(3):491–567, 1977.DOI
  5. [5]V. L. Arlazarov, E. A. Dinic, M. A. Kronrod, and I. A. Faradzev. On economical construction of the transitive closure of a directed graph. Doklady Akademii Nauk SSSR, 194(3):487–488, 1970.
  6. [6]G. D. Birkhoff. The reducibility of maps. Amer. J. Math., 35(2):115–128, 1913.DOI
  7. [7]P. Franklin. The Four Color Problem. Amer. J. Math., 44(3):225–236, 1922.DOI
  8. [8]G. Frederickson. Fast algorithms for shortest paths in planar graphs, with applications. SIAM J. Comput., 16(6):1004–1022, 1987.
  9. [9]Y. Inoue, K.-i. Kawarabayashi, A. Miyashita, B. Mohar, C. Thomassen, and M. Thorup. The four color theorem with linearly many reducible configurations and near-linear algorithm. https://arxiv.org/abs/2603.24880, 2026. Extended Abstract at FOCS’26.
  10. [10]R. Keeler and J. Westbrook. Short encodings of planar graphs and maps. Discrete Applied Mathematics, 58(3):239–252, 1995.DOI
  11. [11]A. B. Kempe. On the geographical problem of the four colours. Amer. J. Math., 2(3):193–220, 1879.DOI
  12. [12]B. W. Kernighan and D. M. Ritchie. The C Programming Language. Prentice-Hall, Englewood Cliffs, NJ, 1978.
  13. [13]P. Klein, S. Mozes, and C. Sommer. Structured recursive separator decompositions for planar graphs in linear time. In Proc. 45th STOC, pages 505–514, 2013. Full version in CORR, arxiv:1208.2223.arxiv.org/abs/1208.2223
  14. [14]I. Maddison. Note on the history of the map-coloring problem. Bull. Amer. Math. Soc., 3:257, 1897.DOI
  15. [15]P. B. Miltersen. Lower bounds for static dictionaries on RAMs with bit operations but no multiplication. In Proceedings of the 23rd International Colloquium on Automata, Languages and Programming (ICALP 1996), volume 1099 of Lecture Notes in Computer Science, pages 442–453. Springer, 1996.DOI
  16. [16]M. Pătraşcu and M. Thorup. Time-space trade-offs for predecessor search. In J. M. Kleinberg, editor, Proceedings of the 38th Annual ACM Symposium on Theory of Computing, Seattle, WA, USA, May 21–23, 2006, pages 232–240. ACM, 2006.DOI
  17. [17]N. Robertson, D. Sanders, P. Seymour, and R. Thomas. The four-colour theorem. J. Combin. Theory Ser. B, 70(1):2–44, 1997.DOI
  18. [18]N. Robertson, D. P. Sanders, P. Seymour, and R. Thomas. Efficiently four-coloring planar graphs. In Proceedings of the Twenty-eighth Annual ACM Symposium on the Theory of Computing (Philadelphia, PA, 1996), pages 571–575. ACM, New York, 1996.DOI
  19. [19]J. P. Steinberger. An unavoidable set of D-reducible configurations. Trans. Amer. Math. Soc., 362(12):6633–6661, 2010.arxiv.org/abs/0905.0043
  20. [20]P. G. Tait. Note on a theorem in geometry of position. Trans. Roy. Soc. Edinburgh, 29:657–660, 1880.DOI
  21. [21]G. Turán. On the succinct representation of graphs. Discrete Applied Mathematics, 8(3):289–294, 1984.DOI

Paper details

vlnc:W_xjhtx5qn
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents