In this paper
AbstractIntroductionGraph theoretic foundationsOur previous workOur contribution: linear time 4-coloringBasicsCoding the recursive -divisionIdentifying Kempe chains4-coloring in linear expected timeDeciding and performing Kempe changes deterministicallyTransferring counters.Our notion of divisions versus those in [13]ReferencesWorksComputer 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 time. We improve it here to 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 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 Kempe changes can be identified and implemented in time. The idea is to spend time to preprocess the graph so that we can identify and simulate each good Kempe change in amortized time. Thus, we implement all Kempe changes in 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 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 in time.
This optimal time bound builds on the graph-theoretic results from [9] which yielded a combinatorial time solution. Our improvement to time is based on a new efficient data structure. More precisely, we use the word RAM model with word length . The unit-cost operations are the standard 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 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 and two colors , , an -colored component is a component of the subgraph of induced by the vertices of color or . To define Kempe chains and changes, we first need to decide a color pairing and with . The Kempe chains are now the - and -colored components. For a Kempe change, we swap the colors on a subset of the Kempe chains; that is, for an -colored component, a swap switches and , and on a -colored component, it switches and . 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 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 , where is a near-triangulation and is the degree function satisfying the following condition: if is a vertex that is not on the boundary of , then ; otherwise . Moreover, if is a cut-vertex of , then .
We say that a plane triangulation contains the configuration if is embedded in such that every inner triangular face of is also a face in , and all triangular faces of have the same orientation in . Moreover, we require that the degree of each vertex in is equal to , that is . Finally, if is a cut vertex in , its two neighbors outside in are non-consecutive around . We say that , or the configuration , is induced in if is an induced subgraph of .
If is a configuration, the free completion of is the near-triangulation obtained from by adding a cycle , disjoint from and joining vertices on the outer face of to in such a way that becomes the outer face of the near-triangulation and such that contains . See the illustration in Figure 1.

Figure 1. A D-reducible configuration with a cut-vertex and its free completion.
The length of the cycle is precisely
where is the length of the outer facial walk of . The cycle is called the ring of the free completion.
Reducible configurations Suppose that contains an induced configuration . Since is induced in , the triangulation contains the free completion of , possibly with some vertices and edges on that may be identified in . Equivalently, when is induced, the embedding of into can be extended to a homomorphism from into , but this homomorphism may not be 1-1 on .
Every 4-coloring of induces a 4-coloring of the ring in the free completion. If this 4-coloring can be extended to a 4-coloring of , then the combination of and gives a 4-coloring of . In the proof of 4CT, special configurations are shown to be reducible. This happens if any 4-coloring can be changed (by using a sequence of Kempe changes in ) so that the resulting coloring extends from to . We describe the precise definition and the process related to Kempe changes next.
We say that a coloring of is 0-extendible (or just extendible) to if it can be extended to a coloring of . For each integer we say that is -extendible to if it is either -extendible or the following holds: If is an arbitrary plane graph containing the ring as a facial cycle and is any 4-coloring of extending , then there is a Kempe change of such that the resulting 4-coloring on after making the Kempe change is an -extendible 4-coloring of . We define the reducibility level (or just level) of as the minimum such that is -extendible. A Kempe change in is called an improving Kempe change if it changes the coloring of to a lower level.
We say that the configuration is -reducible if every 4-coloring of its ring is -extendible, and -reducible means -reducible for some finite . Exercising the definition, we have
Lemma 2 A single vertex of degree 3 or 4 is -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 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 be the ring vertices in the order they appear around . Look at the Kempe chain of induced by the colors of and . If does not include , we simply perform the Kempe change on . Otherwise, connects and , so we can perform a Kempe change on to give it the same color as . In each case, the modified coloring can be extended to . 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 may be contained as a non-induced subgraph of a triangulation . In that case we may not be able to use Kempe-changes to extend a 4-coloring of to . Nevertheless, we still say that the subgraph in 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 from , 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 with a given embedding in , where for each vertex , . Therefore, we will often identify such a configuration with the embedded near-triangulation .
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 , we reduce it and color the rest by induction. This gives a coloring of the ring . If it is an -extendible configuration, then we may have to perform up to improving Kempe changes before we can extend the coloring to the original .
To tell if a Kempe chain is improving, we need to know the level of all colorings of the ring . 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 and of colors and a subset of - and -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 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 , and , , then it can affect the , , , and -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 coloring is an efficient implementation of our previous combinatorial algorithm from [9]. In the following we review the relevant parts of [9]. Let us recall that two subgraphs and of touch if either , or there is an edge with and .
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 , finds one of the following:
(a) A linear number of pairwise non-touching induced D-reducible configurations in , each of which from a given set of size 8202.
(b) A linear number of non-touching obstructing cycles in .
All vertices in the above-mentioned reducible configurations or obstructing cycles have degree at most 12 in . Moreover, for the reducible configurations in , 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 recursion Based on Theorem 3, [9] derived an time 4-coloring algorithm for a planar triangulation of order . For this, it suffices that we can construct in time a planar triangulation that is smaller by a constant factor, color recursively, and use this coloring to color in 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 time. Below we discuss this case.
D-reducible configurations. Suppose as in (a) that we get non-touching induced D-reducible configurations from in . In the quadratic-time algorithm, we would just handle one of them in linear time, but here we will handle all of them in 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 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 of a non-colored configuration gets a 0-extendible coloring, then we extend this 4-coloring of to , and then is no longer among the non-colored configurations.
In general, if the coloring of a ring is -extendible, then we may have to do 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:
Make a random Kempe change. First, we randomly decide the color pairing and that will be used by the Kempe chains, that is, the Kempe chains considered are the - and -colored components. These partition all colored vertices. Next, for every -colored and every -colored component, we toss a coin to decide whether to swap its colors in the random Kempe change.
For all non-colored components whose ring coloring became 0-extendible, we extend the coloring to .
We claim that this algorithm terminates after iterations with high probability. To prove this, we consider an arbitrary non-colored configuration , and argue that its ring coloring will become 0-extendible within rounds with high probability. The result then follows by a union bound.
Consider the iterations from the perspective of any given reducible configuration with ring . If 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 and . There is a 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 and -colored components (Kempe chains) intersecting the ring , of which there are at most . A random Kempe change is thus improving for with probability at least . We need at most 25 such consecutive improvements for for the ring to become 0-extendible. The probability of this success for is at least .
The above fails for if we make a Kempe change that is non-improving for before becomes 0-extendible, but if it fails, we still have a coloring of , and any coloring of is 25-extendible1. If we now do iterations, then the probability that we fail to color is at most . With iterations, this is at most . A union bound implies that all configurations succeed within iterations with probability at least .
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 of a non-colored configuration has a 0-extendible coloring, we extend this 4-coloring of to , and is no longer among the non-colored configurations (strictly speaking, 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 be some (not necessarily all) non-colored reducible configurations in a triangulation that is 4-colored except for the remaining non-colored configurations. The colorings of their rings are not yet 0-extendible.
We can then deterministically, in linear time, find and execute a Kempe change that improves at least a fraction of the rings, and also tell which rings got improved.
Proof. We assume that for every one of our reducible configurations (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 , we use the color pairs and , 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 . Its coloring is only affected by the swap or no-swap of the Kempe chains intersecting it, and there are at most 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 .
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 would be at least , and hence we would expect a fraction of all rings to get improved.
We can get an improvement for at least a fraction 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 only stays live as long as all decided swaps were as it wanted them. If the number of undecided Kempe chains intersecting is , and if all remaining choices were made at random, then the probability that would survive till the end is . Thus, conditioned on decisions made, the expected number of survivors is
We can now pick any undecided Kempe chain . 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 . 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 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 gets an improving move. For the rings whose coloring becomes 0-extendible, we extend the coloring to . 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 for the remaining active rings. After 25 repetitions, we know that there are no active rings left, and that at least a fraction of the original rings have been extended. Conversely, this means that the number of empty rings has been reduced by at least a factor .
We now restart with all the empty rings, all of which are 25-extendible. If we started with reducible configurations, then after at most rounds of 25 Kempe changes, we know that no empty rings remain, hence that we have colored the whole original configuration .
The recursive step, reducing the problem size by a constant factor, is thus completed in time. This suffices for the 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 be a plane triangulation of order with a family of pairwise non-touching induced -reducible configurations in the family from [9]. Find a fast algorithm that selects a subfamily of size such that, for any 4-coloring of , we can (again by the fast algorithm) perform Kempe changes that result in a 4-coloring of which extends to all of .
As described above, using Lemma 4 recursively, [9] solves this task with in time. Moreover, [9] proves:
Theorem 6 ([9]) If we can solve the Color Extension Task 5 of order in time , then we can 4-color any -vertex planar graph in time .
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 Kempe changes in linear total time. The idea is to spend time to preprocess the graph, including the selection of an appropriate subfamily , so that we can identify and simulate each Kempe change in amortized time. Thus, we implement all Kempe changes in 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 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 . It will be important here that a planar graph on vertices can be coded with 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 can tabulate answers to queries, it may be much less useful when the space of queries is larger than . A first formal proof of this is found in [16], which considers using space to support predecessor queries among integers from a range . If , then we can answer queries in constant time with a trivial table. However, if ( bits versus bits for keys in ), then [16] proves that the optimal query time is even in the powerful cell-probe model for static data structures with unlimited preprocessing time.
-divisions. To organize the flow of information, we shall use the recursive -divisions from [8, 13]. Here, an -division of a planar graph divides it into planar subgraphs, each of size at most and boundary of size . From a tabulation perspective, is interesting because the whole subgraph can be coded with -bits, but is also of interest because the boundary is a planar graph that can be coded with -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 -division, the boundary may intersect Kempe chains, but we also have swap/no-swap -bit counters from all live configurations. Even if we are the most optimistic, we need bits of information to cross the boundary. For , this is , 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 and we only have 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 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 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 of objects is a function (all finite binary words). We require that for , . Encoding of is the process of creating or using the code of .
We shall use coding and tabulation in the following classic way. If we can code some subproblems using 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 -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 indices of bits, so we can spend 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 where hides logarithmic factors.
For our analysis, we will work with some power-of-two parameter , and aim to prove that things can be coded using bits. In the end, this means they can be coded with bits for some constant . Choosing a power-of-two parameter , such that , implies that we can tabulate such codes.
One of the important techniques in the coding of information is that if we know an enumeration of objects, e.g., vertices, then we can use an array to associate bits of information with each object using only bits in total. This contrasts the situation where we have to use bits to explain which object some information should be associated with. Here could be a constant, e.g., if the information is a color, but we shall use a super constant if the information is a counter.
Often we shall use an 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 bits, then we prefix this with an bit prefix-free coding of , e.g., a unary description of consisting of 0s followed by a 1, and then follow this by the binary representation of . With this representation, we can uniquely read the objects stored in the code, one at a time.
Divisions. The idea of -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 of a triangulation is a connected subgraph of with at least one edge. The faces of are inner if they are faces of ; 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 forms the boundary .
A division of is a collection of regions such that every face of is an inner face in exactly one region . 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 is on the boundary of , then one of its incident triangles in is in a hole of , and has to be an inner face of another region which then also contains .
An -division of is a division with regions such that every region has at most vertices and at most boundary vertices.
A recursive division is a rooted tree of regions such that the leaves form a division of and the region of any node is the union of its descending leaves. It follows that the root region is itself, and that any maximal anti-chain of regions in the recursive subdivision forms a division. We will also say that the children regions of a region form a division of but their boundaries are still defined via . A face of is inner only if it is an inner face of . If is the depth of the tree, the vertices at depth () are said to be on level in the tree.
Given an exponentially increasing sequence with , a recursive -division of is a recursive division where all leaves are at level 0 and where the regions at level form an -division of . Moreover, regions on level have children on level .
Theorem 8 [13] Let be a planar graph. If , where is a sufficiently large constant, and is an exponentially increasing sequence with , then we can construct a recursive -division of in linear time.
Below we choose to be a sufficiently large power of 2 and define .
For any region , we define an inner face of to be a face of that is not a hole of . All of is thus embedded in the inner faces of .
Coding the recursive -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 of order can be trivially encoded with bits, using -bit labels for the vertices. It is also known [21] that we can get down to bits with an efficient coding as in [10]. We will now show that we can use the recursive subdivision of Theorem 8 to derive an -bit representation of . 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 bits of extra information with each vertex and edge.
We assume that the recursive subdivision 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 visiting children respecting the ordering. The encoding of a region , including the recursive coding of its descendants, will form a consecutive segment of the entire code for .
When we encode a region , we are given labels for the boundary vertices in . We will then produce a coding of prefixed by the length of the code for . The encoding should include the given labels of the boundary vertices so that they can be identified in the encoding.
Consider a level- region . It has boundary vertices with given -bit labels. The region has children where . Let be the graph consisting of the boundary vertices and edges of these child regions. Then is a plane graph of size . We make a local labeling of the vertices of using labels . We want to encode the plane graph by including these local labels plus a mapping from the given boundary labels in to the new labels in . We can easily do this using bits. The encoding for the child region is given our new labels on for its boundary vertices in .
When we decode our encoding top-down, we will already have embedded including the given labeling of its vertices. Since we can identify these vertices in , we can add to the embedding, placing in the inner faces of . This includes our new local labeling of all vertices in , which is used recursively as input for the decoding and embedding of the child regions .
At level 0, a region has constant size, and we encode it explicitly, respecting its boundary labels, using bits.
The reason this is efficient is that on level in the recursive -division, we only have regions, so the space used to get from level to level is bits. The total space over all levels is thus bits. The encoding takes linear time given the recursive division which is constructed in time in [13].
Our encoding describes both and the ordered recursive division . 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 bits in total.
More efficient encoding of boundaries We will now improve the coding of boundaries. A region on level has boundary vertices, including the boundary vertices of its children. Above we encoded it with bits using 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 is placed in the graph representing . We will now get down to bits exploiting that a region has only a constant number of holes.
Suppose we have a plane graph whose edges are the edges on the boundary of a hole plus an oriented start edge , 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 is followed by edge where is the neighbor of in that follows anti-clockwise. An important point in the description of the above boundary walk is that given the oriented edge , we do not need any further description of the hole, since the walk defines the hole.
Now consider a region with holes with boundaries . Then . To represent the above hole walks, we just need to store for each edge in which boundary it belongs to, and whether it is the start edge and, if so, with what orientation. We call this information the hole information associated with each edge of , 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 in our recursive subdivision. With the above information, we also have a unique enumeration of the vertices and edges in : we do the walks of , 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 with children , and our goal is to encode all their boundaries in such a way that we can identify boundary vertices of the parent region among the boundary vertices of the children . We shall refer to this as the boundary structure .
First we encode the plane graph , which we note includes . 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 we add a linear number of auxiliary edges, so as to create a 2-connected triangulation . We now get the encoding of 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 , we store if it is an auxiliary edge. If not, for , we store if it belongs to and if so, its hole information in . 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 using only bits.
To clarify the parent-child relation, note that the boundary of each region 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 , including the associated hole information, and this provides a complete map between the hole walks of 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 and its children . We shall sometimes use this boundary structure coding when is contained inside a larger planar graph .
Lemma 9 For a region with children , suppose we have a plane graph containing . Then we can encode using bits so that, for each , we can identify the hole walks of in .
Proof Add auxiliary edges to triangulate 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 it belongs, and the hole information for that . From this, after decoding , we recover every together with its enumeration. The total number of bits is .
The point is that below we are going to augment 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 of reducible configurations. We are only going to use the recursive -division down to some where where is the parameter to be chosen later such that, informally speaking, .
An region thus has at most vertices, implying that we can encode it with bits, including a coloring of the vertices. There are at most 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 time.
Recall from Task 5 that we are given a family of non-touching induced D-reducible configurations, and that we have to select a subfamily of linear size. We select
The total number of boundary vertices of leaf regions is . Since our reducible configurations are non-touching and each has only a constant number of vertices, we still have reducible configurations for which no vertex is a boundary vertex of a leaf region. These are the reducible configurations in . If is in the region , then its ring vertices may intersect , but its completion , that is completed with its ring, is still contained in .
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 with . As described above, we can encode these boundary structures using 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 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 based on given opposing color pairs and with . We will only spend 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 time by spending constant time on regions at levels , that is, starting from the leaf regions. We have such regions. For , the boundary size is , and here we will spend time. For the whole level, this is , so level dominates3 with a cost of .
Kempe connectivity via Kempe edges From now on, we fix complementary pairs and of colors. The Kempe chains only involve the colored vertices. Since we have a proper coloring, there are no monochromatic edges, so the -Kempe chains are the -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 - and -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 and of the same plane graphs, e.g., could be the boundary of a region of (and could consist of some Kempe chains). We need an operation that contracts the Kempe chains from in the faces of . The resulting graph, denoted , is a plane graph of size containing and such that any two nodes from are Kempe connected in if and only if they are Kempe connected in . Figure 3 shows an example with for some region in .
Figure 3. The figure shows the graph 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 .
We consider one face of at a time. First we delete all parts of in that are not Kempe connected to . Next, for each appearance of a vertex on the boundary of , having some incident edges in , we make a copy inside , attached to by a new Kempe edge , called an “attachment edge”. This edge is attached to the boundary of at the same appearance of . Moreover, we move each Kempe edge so it becomes a Kempe edge . Note that if the same vertex appears multiple times along the boundary of , then we make a separate copy with a separate attachment edge. Also note that if we had an edge contained in and with both end-points in the boundary, then it will become an edge . When we are done, we have moved all original Kempe edges in so that they are now embedded strictly inside . Finally, we contract all Kempe edges strictly inside , calling the result Kempe nodes. The new attachment edges now connect each boundary vertex of with a Kempe node. The Kempe nodes and the attachment edges now provide exactly the same Kempe connections between boundary vertices of (and in all ) as did the Kempe edges from in . Doing this operation on all faces of , we get the graph . Finally we argue that . The point is that for each vertex , we add at most one each time a boundary walk of visits . The number of such vertices added in is at most the total length of the boundary walks of . 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 . Thus we have proved
Lemma 10 Let be the contraction of the Kempe edges from in the faces of . Then is a plane graph of size such that any two vertices in are Kempe connected in if and only if they are Kempe connected in .
Figure 2. The figure shows parts of a 4-colored graph with a region (light gray background) and its boundary (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 is supposed to be triangulated, so the drawing only includes some illustrative parts of . Also, the illustration does not include reducible configurations that are not colored (they do not intersect any boundaries).
Final goal For every region , we will compute both and (see Figure 3). Note that excludes all vertices strictly contained in since they are not (Kempe) connected to in . We also note that , but we compute and separately. We compute bottom-up, and using them, we will compute the top-down. Note that for a leaf region , we can use to find out which vertices in are Kempe connected in . In particular, if we have a reducible configuration strictly contained in , then we can see which of its ring vertices are Kempe connected, and since has size , this can be done simultaneously for all such configurations in with a single table look-up.
Figure 4. We produce (left) bottom-up, and then (right) top-down, and finally combine them to produce (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 . Given the encoding of a leaf region and its coloring, we can compute with a table look-up.
Above the leaf-level, consider a region with child regions . From each child, we get the (encoding of the) graph . Let be the union of these graphs. Then
The basic point here is that if is of level , then the above only involves boundaries of order . For small regions of levels , the size is at most , but the boundary size is only , so the computations can be done by table look-ups.
As we go regions on levels , we compute in time linear in the total size of the graphs involved in the bottom-up step (2), which is . For the whole level , this is time. Since this is only for where , the total cost of the bottom-up processing is .
Top-down processing Having computed for all regions on or above leaf-level , we now wish to compute all in a top-down processing. The top-most region is , which has no boundary, so there is nothing to compute.
Suppose we have computed for a region with child regions . We compute as follows. Let . Then
As for the bottom-up processing, the top-down processing is easily implemented in total time. As we described the final goal, when we for each leaf region have its coloring and , then we know which of its vertices are in the same Kempe chains, and since this is all encoded in -bits, we can get the information with table look-ups.
Enumeration of Kempe chains Consider a non-leaf region with child regions and let , noting that . In our bottom-up processing, we computed the \partial R_j^{\mathcal{K}}_{R_j} for , and afterwards, top-down we computed \partial R_0^{\mathcal{K}}_{G-E(R_0)}. Putting them together, we get
With this information, which only takes bits, we know precisely where different Kempe chains intersect . We divide the Kempe chains intersecting into two types. Those who intersect and those who don’t. The latter type are said to stop in . Equivalently, a Kempe chain stops in if and only if it is strictly contained in (that is, contained in ), but not strictly contained in any child of .
Generally, if we have an enumeration order on a set of vertices , then it induces an enumeration order of the Kempe chains intersecting ; namely, the order in which they are first encountered.
Recall that our boundary structure provides unique enumeration of the vertices in , as well as an enumeration of the vertices in each . This then induces orderings of the intersecting Kempe chains, and all this information is implicit when we combine with . This is all represented in bits if is on level .
Combining this information with the corresponding information from the parent of , we can follow how the same Kempe chains appear in the different enumeration orders.
For a leaf region , we identify all intersecting Kempe chains from together with , all represented in bits. The Kempe chains are enumerated as above. The Kempe chains strictly contained in a leaf region are said to stop in . Then every Kempe chain in stops in exactly one region.
Implementing Kempe changes For every region in our recursive subdivision, we have an enumeration of the Kempe chains stopping in . 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 .
The implementation of the Kempe changes is done top-down. Consider a region . We had an enumeration of the Kempe chains intersecting , 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 . If had children , then for each child , we need to translate from these bit-strings to a bit-string for the Kempe chains intersecting following their enumeration for . However, we know the translation from and where .
If is on level , then this involves Kempe chains, and all the information can be described using bits. On levels such that , we have , so the translation can be done with a table look-up. On the high level, for , the translation is trivially done in time.
When we get to a leaf region , from above, we get the bit string deciding the changes for Kempe chains intersecting , and we combine this with the bit strings for the Kempe chains strictly contained in . We now know exactly which vertices in 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 . All these colors are found in the color array for vertices in . Using a single table look-up based on , , 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 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 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 , we just need to generate a random bit string specifying the random choices for all Kempe chains stopping in . The total number of Kempe chains is at most . Assuming that we can generate a random word with bits in constant time, we generate all the bits in time. Having specified the random Kempe change, we can implement it as described above in time.
Next, we need to check which of the uncolored reducible configurations from have become 0-extendible so that can now be colored. Since they are all strictly contained in leaf regions, we can just check one leaf region at a time. It is represented with bits, including the new coloring, so with a simple look-up, we perform this task for all the relevant configurations strictly contained in in constant time.
As described in § 1.2, we are done with high probability after iterations (and one iteration (Kempe change) takes time), thus spending 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 to :
Lemma 11 Let be some (not necessarily all) non-colored reducible configurations (from the family selected in § 2.1) in a triangulation that is 4-colored except for the remaining non-colored configurations in . The colorings of their rings are not yet 0-extendible. Suppose also that we have computed the recursive division with all the boundary structures from above (this took linear time, but was only done once in the preprocessing). Finally, we assume that the participating configurations are marked in the coded leaf representations, so that we do not need to handle them individually.
We can then, deterministically in time, find and execute a Kempe change that is improving for at least a fraction 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 and decided, we go through the - and -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,
where is the number of undecided Kempe chains touching .
When deciding on a Kempe change , we only need the sum restricted to live configurations touching . Deciding may kill many of these configurations, but for those that are touched by but not killed, the survival probability is doubled. Since we always have , we note that the expectancy is always an integer multiple of . 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 if there exists a Kempe change that is improving for ; for then 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 that is strictly contained in some leaf region , and all we need to know is how the Kempe chains partition the ring of . From the local perspective of , 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 in , we know which swaps are improving.
To find out how Kempe chains connect vertices in , we just have to consider , where is as computed as in § 2.2. We note that is represented in 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 , we assume that we have already made decisions for all Kempe chains stopping below , so when we get to , we only have to make decisions for Kempe chains stopping in . However, to make the right decision on , we need to know about all the live configurations touching .
It is now important to note that we only consider reducible configurations strictly contained in leaf regions, so they cannot intersect the boundary of any region. Therefore, can only touch configurations strictly contained in .
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 . A Kempe chain stops in if and only if is strictly contained in . Since we only consider reducible configurations strictly within regions, can only touch reducible configurations strictly within . All the relevant information is therefore contained in , including prior decisions on Kempe chains in . In principle, we want to decide one such Kempe change at a time, but we can simulate this sequential process for all of them, just using the information from . Using a table, taking and the original coloring of as input, we can produce a bit vector of decisions.
However, for each of the at most Kempe chains intersecting , 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 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 of these even for a single Kempe chain. We want to argue that the information needed for the decisions can be contained in counters.
We need to consider reducible configurations that touch some Kempe chains from and which are alive before we make switch decisions on . Relative to our Kempe batch , the main type of such a reducible configuration is the set of Kempe chains from that touches. We claim that the number of main types relative to is only . To see this, we construct a plane graph representation as follows. We contract each Kempe chain from 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 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 . 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 be the number of black vertices. If , the statement is immediate since there are at most different sets of black neighbors. Assume . There are at most 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 black vertices, and hence there are at most white vertices of degree 2.
Let 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 vertices and at least edges. Hence by Euler’s formula for triangle-free planar graphs,
so . Thus there are at most 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 touches different Kempe chains from , then the subtype tells which of these should be swapped to get the preferred improving Kempe changes for . There are options.
The subtype also tells the number of undecided Kempe chains outside that touches. Then is bounded by the ring size, which is at most 18. Therefore, the number of subtypes is at most .
Each configuration node in 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 .
With the above representation in place, we will now decide on the changes for our Kempe chains . Before we decide on , the expected number of surviving configurations touched by is a sum over all types (main types with subtypes). To contribute, the main type should touch and for the subtype, the preferred swap decisions on should agree with those we made. If the main type touches Kempe chains in , then its survival probability is , so the contribution is the counter times .
When we decide on , 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 , and if so, maintain the above number of undecided Kempe chains it touches. Then, when we make the decision on , we only involve the configuration types touching . Since the number of configuration types is and each only touches Kempe chains, the total time needed to decide on is if we use a simple combinatorial algorithm.
Also, if we can represent with all its counters in 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 of Kempe chains, the main type of a configuration is the subset of that it touches. Recall that our description of 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 . However, for the representation of Kempe chains intersecting the boundary of , instead of contracting these Kempe chains completely, we will use the plane graph where the Kempe chains in intersecting are only contracted inside the faces of .
We will augment the graph with configuration nodes from the main types from relative to the Kempe chains intersecting . More precisely, we construct as follows. From , we keep an arbitrary configuration from each main type relative to the Kempe chains intersecting . No other configurations from are relevant. We contract each main-type configuration as we constructed . 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 of the Kempe chains intersecting . What remains is with Kempe nodes and main type configuration nodes in the faces.
The number of Kempe chains intersecting is bounded by the size of , 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 and we already know that has size , so we conclude that has size .
Our representation of came with an enumeration of the Kempe chains intersecting , and in , we can see the Kempe chains touched by a configuration node. We now get a natural enumeration of the main configuration types in . For each main type of a configuration , we first sort the indices of the Kempe chains touched by . Second, we order the main types lexicographically with respect to these sorted lists. Thus we get an enumeration of all main configuration types in .
Figure 5. The figure of . There are three main configuration types: , , , and each counter is 5, 1 or 2. For simplicity, subtypes are ignored in these counts.
Now we consider a region with child regions . Our goal is to construct given for each child . Let , and recall that . From (4) we have
When we combine with the boundary structure , we have all the information needed to follow how the Kempe chains intersect the boundaries of the holes of each individual boundary , including the parent boundary .
We now want to construct which is with a configuration node from each main type in added. We will construct it from the that we get from the child regions .
We want to fill all the faces of . Either is a hole of , an empty triangle of , or an inner face of some . If is a hole of , then is outside and then we just copy in the Kempe nodes from . If is an inner face of some , we simply copy the configuration of Kempe nodes and main type configuration nodes from this face in . As a final cleaning step, note that we, from different , may have configurations of the same main type. In this case, we delete all but one of them.
From , we can easily construct and , where consists of the Kempe chains stopping in . To get we essentially just delete all Kempe chains in from since these are exactly the Kempe chains that do not intersect . Next, inside each inner face of , we contract the remaining Kempe components to single Kempe nodes. Finally, since we have removed the Kempe chains from , 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 is similar, but this time, remove the Kempe chains from that are not in .
We let denote the combination of all the above information. It provides us for , and it tells us how to translate between the enumerations of Kempe chains and main configuration types in the different , as well as for .
In the following bounds for the combined structure, let be the level of ; the total size of the parent and child boundaries is . Note that all the above information in is coded in planar graphs of total size , hence represented with bits. We claim that we can also compute in 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 is represented as the sorted list of some of the Kempe chains from that are touched by . These Kempe chains are indexed within , so all relevant indices are . The list has constant length because 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 . We can therefore sort the main types lexicographically in 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 in time. As usual, we note that if , 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 with children . Inductively, what we get from each is , which has a configuration node of each main type relative to the Kempe chains intersecting . Such a configuration node represents all live configurations touching the same subset of these Kempe chains. When we say that is live, we mean that its preferred improving change agrees with all the swap decisions made for Kempe chains stopping below . The live configurations represented by 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 . These are the only undecided Kempe chains that they touch. If 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 can be easily extended to the subtypes, and then the counters are all contained in an array . We get such an array from each child , and in the recursive step we fill out for .
With , we will now construct , this time including subtypes with counters. Several child structures 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 where are the Kempe chains stopping in . Each main type from touched a subset of the Kempe chains intersecting . From this set, we get a reduced type that removes all Kempe chains not in , so the reduced type only tells which Kempe chains from it touches.
Now consider the subtypes of . They are determined by the preferred swap decisions for all Kempe chains intersecting that they touch. They only need preferred swap decisions for the Kempe chains from that they touch. However, the subtype also counts the number of undecided Kempe chains touched by
| Look-up | Additional input | Iterations |
| Construct | The segment | |
| Update | , , , and current | |
| Decide swaps for | and populated | |
| Update | Completed , , and current |
caption: The table summarizes the look-up steps in the order they are done for the processing of the region . Whenever required, the input also contains , the relevant segment indices and lengths, the counter width, and the length of the decided prefix in . All these inputs, together with any one source array segment and one target array segment, occupy bits.
:::
the configuration that intersect and are not in .
We now have all the counters needed to make the swap decisions for the Kempe chains in , and we record these decisions.
The next step is to remove Kempe chains in from . First we have to remove all subtypes not agreeing with the decisions we just made on . The remaining subtypes are only distinguished by the decisions on Kempe chains touching , and then we can construct 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 , completing the recursive step.
Even including counters of subtypes, a simple algorithm can do the above processing of in time . As usual, this suffices if is on level with .
However, with counters, we must process more information. If is a region on level , then the counters for subtypes may need bits, so the total space is , and if this is , then we cannot do the processing just using a look-up table. This means that we can only use simple table look-ups for . Below, we handle the remaining cases.
Transferring counters.
We will now show how to handle regions on level where
Let be an integer such that . Then 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 time. There are such regions, so the total time for all these regions becomes , 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 on level with children . Together with each child , we have in bits plus the array of counters for all types in . The total processing of is summarized in Table 1.
Let be Kempe chains stopping in . We already know how to compute with a single table look-up, and this includes all the main types relative to . However, to make the swap decisions for , we need all the subtype counters from .
The simple idea now is that we partition into segments each with Kempe chains, and make the swap decisions for one segment at a time. The point here is that an array of counters, each with bits, fits in bits, and this can be used for a table look-up. As we proceed, we add the decisions to one swap decision vector for all of . The vector is stored in bits.
To make the decisions for , we first construct describing the configuration types relevant to . By Lemma 12, there are only main types, and only a constant factor more subtypes. We will populate a corresponding counter array , noting that it only needs bits. When has been populated, we can make the swap decisions for using a single table look-up.
From and , we have all the information we need to map type indices from the to type indices from . Combining this with the vector of prior swap decisions for , we also know which subtypes should be eliminated because they did not agree with the prior decision.
We now also divide into segments of counters. One such segment is stored in bits. If we combine this with , , , and , then we know how to update with the counters from . This is only bits of information, so we can compute updated with using a single look-up.
We have to update using the counters from all segments in all , but there are only such segments in total, so we need only table look-ups. When done populating , we make the swap decisions for as described above using a single table look-up.
We have to repeat this for each of the segments of Kempe chains stopping in . The total number of table look-ups to compute all swap decisions for is therefore , as claimed.
Next, to complete the recursive step, we need to compute the array of subtype counters for . We use the exact same idea as above, dividing into segments . Using , , , and , we know to update with , and we can again do this with a single table look-up. The total number of segment pairs considered is . We conclude that we can complete the recursive step for in 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 -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 is a collection of regions . In this paper, we require that every face of is an inner face of exactly one region .
In [13] they only require that every edge in 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 of . If none of them contain , then they each have a side of 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 . As noted in § 2, with our requirements for divisions, an edge is on a hole of (our definition of a boundary edge) if and only if is shared with another region (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 to know its boundary . 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 , in step 7, they find a simple-cycle separator . This is a simple cycle in the graph where they have placed a star in each hole of . This means the cycle follows edges of 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 and . For , we have a child region consisting of all parts of contained in . In particular, this implies that we get a bipartition of the inner faces of . Inductively, it follows that if we start from where all faces of 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 . They only include edges on the sides of the inner faces or in , but as we can see in their Figure 1 (d), we can get edges with holes on both sides, and if had such an edge that is not in , then [13] would not pass 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 and by giving them all parts of contained in and , respectively.
Bound on the number of children A final difference is that we state that regions on level have children on level . This bound is not in [13], but it follows by a modification of their proof in [13 §3.3] that their -division has only regions where (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 . Each node represents a region . Let and . For , let be the set of the highest descendants of such that (possibly ). The regions represented by form a division, but not yet an -division. Next let be the set of the highest descendants of such that for some constant . Finally define . Relating back to our levels, if is a region on level then its child regions on level form the set . Moreover, by definition of level , and .
For general and , we will argue that . In [13 §3.3] they argue that if is on depth 0 (mod 3) in , then . 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 .
Next we want to argue that . In [13], they argue this (for the special case where is the root with ) by referring to the parents of of , since they have . However, these parents can overlap a lot, e.g., could have another child containing almost all of , and with a child . We therefore present a different proof that fixes this issue in [13].
Lemma 13 .
Proof We want to argue that a constant fraction of the nodes have .
Consider any node with children and . We assume is bigger than some large enough constant. From the construction in [13], we have some simple inequalities. Since and divide with some overlap, we have and . Moreover, if is at depth 0 mod 3 in , then by [13 (2)],
This also implies
Now consider the subtree of rooted in and containing all nodes with . The parents of nodes are exactly the nodes in with fewer than two children. Also, . Moreover, if is a leaf in , then it has at least one child with .
We need to argue that the size of is linear in the number of leaves. To do that, we will bound the maximal length of a path of single-child-nodes in .
Every third node on such a path is at depth 0 mod 3, and if , then by (6), the children have , so both children are in , that is, is a branching node.
However, if and is at depth 0 mod 3, then, by (5), both children have . This means that after passing at most 8 such nodes, all children have , implying that they are not in , i.e., that we have reached a leaf. We conclude that the maximal single-child-path in is of length 24, hence that the total number of nodes in is linear in the number of leaves. This completes the proof that a constant fraction of the nodes have .
Since only boundary vertices are shared in the division represented by , we know that
Since a constant fraction of the nodes have , we conclude that .
By [13 (13)], for every , we have , so we conclude that
Finally, we insert , , and , and get .
References
- [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]K. Appel and W. Haken. Every planar map is four colorable. I. Discharging. Illinois J. Math., 21(3):429–490, 1977.DOI
- [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]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]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]G. D. Birkhoff. The reducibility of maps. Amer. J. Math., 35(2):115–128, 1913.DOI
- [7]P. Franklin. The Four Color Problem. Amer. J. Math., 44(3):225–236, 1922.DOI
- [8]G. Frederickson. Fast algorithms for shortest paths in planar graphs, with applications. SIAM J. Comput., 16(6):1004–1022, 1987.
- [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]R. Keeler and J. Westbrook. Short encodings of planar graphs and maps. Discrete Applied Mathematics, 58(3):239–252, 1995.DOI
- [11]A. B. Kempe. On the geographical problem of the four colours. Amer. J. Math., 2(3):193–220, 1879.DOI
- [12]B. W. Kernighan and D. M. Ritchie. The C Programming Language. Prentice-Hall, Englewood Cliffs, NJ, 1978.
- [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]I. Maddison. Note on the history of the map-coloring problem. Bull. Amer. Math. Soc., 3:257, 1897.DOI
- [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]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]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]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]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]P. G. Tait. Note on a theorem in geometry of position. Trans. Roy. Soc. Edinburgh, 29:657–660, 1880.DOI
- [21]G. Turán. On the succinct representation of graphs. Discrete Applied Mathematics, 8(3):289–294, 1984.DOI



