The Balanced Four-Color Theorem
July 14, 2026
Abstract
We show that every planar graph with \(n \geq 3\) vertices admits a 4-coloring in which each color is used on fewer than \(n/2\) vertices. This bound is the best possible. Moreover, such a coloring can be found in \(O(n \log n)\) time. We also extend these results to five or more colors and to graphs on general surfaces.
1 Introduction↩︎
Starting with the celebrated four-color theorem, which states that every planar graph is 4-colorable, the graph coloring problem, which asks for coloring each vertex of a graph \(G = (V, E)\) with a minimum number of colors so that no two adjacent vertices have the same color, has been one of the most fundamental problems in graph theory and algorithms. The four-color theorem had been open for more than a century until Appel and Haken [1] finally proved it in 1976, and it is now considered one of the most famous theorems in all of mathematics.
In this paper, we revisit the four-color theorem. The proof, as well as its later constructive proofs [2], [3], yields only a single coloring, which may be inflexible. Indeed, the only planar graphs that yield a unique 4-coloring are Apollonian networks, characterized by Fowler [4].
Therefore, we consider a somewhat different direction; here comes into the spotlight: “How can we obtain a ‘balanced’ 4-coloring?” This question is related to equitable coloring, a well-studied topic in extremal graph theory since the 1960s [5]–[9], which we briefly discuss below. Moreover, coloring graphs in a balanced way has many applications, including balanced allocation, work sharing, and load balancing, for example, in scheduling [10], [11], clustering [12], register allocation [13], and bandwidth allocation [14].
1.1 Equitable Coloring↩︎
For a graph \(G = (V, E)\), its \(k\)-coloring is equitable if the number of vertices of each color differs by at most one. One of the most fundamental results in extremal graph theory concerns equitable coloring: every graph with maximum degree \(\Delta\) has an equitable \(k\)-coloring for all \(k \geq \Delta+1\), which was conjectured by Erdős in 1964 [6] and proved by Hajnal and Szemerédi in 1970 [8], [15] (indeed, this result was originally proved in terms of clique packing, i.e., a spanning collection of vertex-disjoint cliques). There have also been a number of studies on equitable coloring beyond graphs with maximum degree \(\Delta\); one example is the work in [16] on \(d\)-degenerate graphs.
1.2 The Four-Color Theorem and “Balanced” Coloring↩︎
Returning to the original motivation, we ask whether a balanced \(4\)-coloring of a planar graph exists. As an example, consider the bipartite graph \(K_{2,n-2}\) with one extra edge, say \(\{v_1, v_2\}\), in the partite set of two vertices. This graph has no equitable \(4\)-coloring (when \(n \geq 7\)), because if we use color \(1\) on \(v_1\) and color \(2\) on \(v_2\), we can only use colors \(3\) and \(4\) on the remaining \(n-2\) vertices. Thus, on one hand, the answer to the question is “no”. However, on the other hand, if we interpret it as the question of whether each color class can be meaningfully small, the answer might be “yes” — this graph still has a \(4\)-coloring in which colors \(3, 4\) are each used on fewer than \(n/2\) vertices (1); every planar graph might admit a meaningfully balanced \(4\)-coloring.
Despite the motivation, to the best of our knowledge, there was no prior research on how balanced \(4\)-colorings of planar graphs can be achieved. One reason may be that the complexity of the proof of the four-color theorem impedes attempts to strengthen the theorem; [3] already shows that a generalization of the four-color theorem is highly non-trivial. Another reason may be that the graph theory community has mainly focused on equitable coloring: for example, bounded coloring [17], which aims to minimize the number of colors when the size of each color class is bounded, has not been studied as extensively as equitable coloring.
Let us point out that, given the relationship between equitable coloring and fair division [18], a hot topic in algorithmic game theory, achieving approximately balanced colorings is a natural line of research in this sense, just as fair division focuses on approximate fairness [19].
1.3 Color-Critical Graphs↩︎
It is essential to mention the concept of color-critical graphs to discuss the background of this question. A graph \(G\) is called \((k+1)\)-critical if \(G\) is not \(k\)-colorable but any proper subgraph is. Using this concept, we can create a \(k\)-colorable graph (which is less obvious than \(K_{1,1,n-2}\)) such that every \(k\)-coloring has a color class of size at least around \(\frac{n}{k-2}\); indeed, we use a \((k+1)\)-critical graph \(H\) as a “gadget”. From \(H\), we delete an arbitrary edge \(e = \{a, b\}\), and instead we add a new vertex \(c\) and draw an edge \(\{a, c\}\). Then, we merge this graph with \(K_{2,t}\), gluing along vertices \(\{b, c\}\) and the partite set of two vertices; see 2 for an example.
Since every \(k\)-coloring of \(H-e\) must assign the same color to \(a\) and \(b\) (due to criticality), it must assign different colors to \(b\) and \(c\). Therefore, only the remaining \(k-2\) colors can be used on the partite set of \(t\) vertices, and hence every \(k\)-coloring has a color class of size at least \(\frac{t}{k-2}\).
On the other hand, color-critical graphs lead to deep (algorithmic) results in topological graph theory, especially for graphs on surfaces. Let us contrast the plane and a general surface:
Planar graphs: by the four-color theorem, every graph is \(4\)-colorable (so no 5-color-critical planar graphs exist).
Graphs on a surface: although the chromatic number can be very large, by the deep result of Thomassen [20], there are only finitely many \(6\)-color-critical graphs that can be embedded in any orientable surface. Therefore, one can check if a graph embedded in a fixed surface is \(5\)-colorable in polynomial time.
Therefore, exploring \(5\)-coloring for graphs on a surface is a significant question, as is \(4\)-coloring for planar graphs. We shall present balanced colorings for each of these cases.
1.4 Our Contributions↩︎
In this paper, we address the question of how balanced the \(4\)-coloring of planar graphs can be. Our main result is described as follows:
- Main Result.
-
Every planar graph with \(n \geq 3\) vertices admits a \(4\)-coloring such that each color is used on fewer than \(n/2\) vertices, and such a coloring can be computed in \(O(n \log n)\) time.
We will not dig into the details of the proof of the four-color theorem; rather, we use this theorem as a “black box” tool. Our strategy is as follows: we first compute an arbitrary \(4\)-coloring with an \(O(n \log n)\)-time algorithm by [3], and then we iteratively improve it to make it more balanced by utilizing Kempe chains [21], which is a tool well-known for the four-color theorem. We refer to it as the Kempe change, the operation of interchanging two colors in a Kempe chain; this idea has also been studied in reconfiguration problems for graph coloring beyond planar graphs [22], [23]. In short, we show that \(O(\log n)\) iterations of Kempe changes is enough to make the coloring sufficiently balanced; since each iteration takes \(O(n)\) time, we achieve \(O(n \log n)\) time in total.
Strictly speaking, we show the following technical theorem (for \(k\)-coloring) involving a new parameter \(\alpha\), which allows us to extend the result to other surfaces; we use \(\alpha = -4\) for planar graphs. With \(k = 4\), by combining this theorem with [3], we obtain our main result above.
Theorem 1. Let \(\alpha \geq -4\) be a constant parameter and \(k \geq 3\). Let \(G\) be a \(k\)-colorable graph of \(n \geq 3\) vertices, such that for all its bipartite subgraphs \(H\) with 3 or more vertices, \(|E(H)| \leq 2 |V(H)| + \alpha\) holds. Given \(G = (V, E)\) together with a \(k\)-coloring \(\varphi: V \to \{1, \dots, k\}\), one can compute a \(k\)-coloring of \(G\) such that each color is used on at most \(\left\lceil \frac{n+\alpha+2}{k-2} \right\rceil\) vertices, in \(O(kn \log n)\) time.
We note that the threshold is \(\left\lceil \frac{n-2}{k-2} \right\rceil\) for planar graphs, due to \(\alpha = -4\). Meanwhile, for a planar graph \(K_{1,1,n-2}\) (see 1), one color is used on \(\left\lceil \frac{n-2}{k-2} \right\rceil\) or more vertices in every \(k\)-coloring. Therefore, the bound above is the best possible, for all \(n \geq 3\) and \(k \geq 3\).
1.5 Organization of the Paper↩︎
In 2, we present the preliminaries needed for the proof. In 3, we present an overview of the proof and the algorithm. In 4, we present the proof of the main technical theorem and the algorithm. In 5, we state the implications of the main technical theorem for planar graphs and other surfaces (e.g., projective plane and torus). Finally, in 6, we conclude this paper by mentioning several conjectures.
2 Preliminaries↩︎
2.0.0.1 Convention and Notation.
In this paper, we consider an undirected simple graph \(G = (V, E)\), which has no self-loops and no multiple edges. The sets of vertices and edges of \(G\) are also denoted by \(V(G)\) and \(E(G)\), respectively. The degree of a vertex \(v \in V\) in \(G\) is denoted by \(d(v)\) or \(d_G(v)\). The induced subgraph of \(G\) on a vertex set \(S \subseteq V\) is denoted by \(G[S]\). We identify each component of \(G\) with its vertex set \(C \subseteq V\).
2.0.0.2 Kempe Change.
Let \(\varphi: V \to \{1, \dots, k\}\) be a coloring of \(G = (V, E)\). Let \(V_i := \{v \in V : \varphi(v) = i\}\) be the set of vertices of color \(i\). A Kempe change is an operation that chooses two colors \(a, b\) and a component \(C \subseteq V_a \cup V_b\) of the induced subgraph \(G[V_a \cup V_b]\), and then recolors each vertex in \(C\) from \(a\) to \(b\), and from \(b\) to \(a\). 3 shows an example. Trivially, the resulting coloring after Kempe change is proper, i.e., no two adjacent vertices have the same color.
3 Strategies and Intuitions↩︎
In this section, we sketch the idea of our proof for the main result: every planar graph \(G = (V, E)\) with \(n \geq 3\) vertices admits a \(4\)-coloring such that each color is used on fewer than \(n/2\) vertices.
3.1 Overall Strategy↩︎
The overall strategy is to first obtain an arbitrary \(4\)-coloring \(\varphi: V \to \{1, 2, 3, 4\}\), and then repeatedly improve the coloring \(\varphi\) by Kempe changes. For simplicity, we always assume, w.l.o.g., that color \(1\) is the most frequently used. Also, for \(i = 1, 2, 3, 4\), let \(V_i := \{v \in V : \varphi(v) = i\}\) be the set of vertices of color \(i\). In order to make sure that \(\varphi\) finally becomes a coloring in which each color is used on fewer than \(n/2\) vertices, all we need to prove is the following: “if \(|V_1| \geq n/2\), there exists a Kempe change involving color \(1\) that decreases the size of the largest color class.”
3.2 Idea 1: “All Connected” is Impossible↩︎
When it is impossible to improve the coloring by a Kempe change, what would the coloring look like? For \(i = 2, 3, 4\), let \(H_i := G[V_1 \cup V_i]\) be the induced subgraph on vertices of colors \(1\) and \(i\). A leading “impossible” example is when \(H_2, H_3, H_4\) are all connected — in this case, a Kempe change on \(H_i\) simply interchanges colors \(1\) and \(i\) in the entire coloring \(\varphi\), resulting in no improvement.
The good news is that, as long as \(|V_1| \geq n/2\), this case cannot happen. We prove this in what follows, but before that, we define a graph \(H := H_2 \cup H_3 \cup H_4\). Note that \(H\) consists of all vertices in \(G\), and the edges in \(G\) where one endpoint has color \(1\). Then, \(H\) is a bipartite graph, which can be divided into two parts \(V_1\) and \(V_2 \cup V_3 \cup V_4\).
Proposition 1 ([24]). Every bipartite planar graph with \(n \geq 3\) vertices has at most \(2n-4\) edges.
Proposition 2. Assuming \(|V_1| \geq n/2\), at least one of \(H_2, H_3, H_4\) is not connected.
Proof. Suppose \(H_2, H_3, H_4\) are all connected. Then we have \(|E(H_i)| \geq |V(H_i)| - 1 = |V_1| + |V_i| - 1\) for each \(i\). Therefore, the total number of edges is at least \[|E(H)| \geq \sum_{i=2}^4 (|V_1|+|V_i|-1) = 2 |V_1| + \sum_{i=1}^4 |V_i| - 3 = 2 |V_1| + n - 3\] However, \(|E(H)| \leq 2n-4\) due to 1. Hence, we obtain \(2 |V_1| + n - 3 \leq 2n-4\), which yields \(|V_1| \leq \frac{n-1}{2}\). Since \(|V_1|\) and \(n\) are integers, the actual bound is \(|V_1| < n/2\), which contradicts the assumption (see 4). Therefore, at least one of \(H_2, H_3, H_4\) is not connected. ◻
3.3 Idea 2: The Penalty for Deviations↩︎
While 2 gives the intuition that the \(n/2\) bound may be achievable, there might be some cases where, even if some \(H_i\) is not connected, no Kempe changes can improve the coloring. However, in this case, the number of vertices of color \(1\) versus color \(i\) must be highly imbalanced across the components of \(H_i\). In particular, one can show that there must exist a component \(C \subseteq V_1 \cup V_i\) of \(H_i\) such that \(|C \cap V_i| \geq |C \cap V_1|\) (cf. 6).
Let us consider what the existence of such a component \(C\) triggers. As seen in the proof of 2, the bound on improving the coloring by Kempe change is based on the fact that \(H\) can have at most \(2n-4\) edges. Apparently, the more edges in \(H\), the less freedom to improve the coloring by Kempe changes. However, the following happens:
If \(H_i[C]\) is not a tree: The set of possible Kempe changes remains unchanged even if we remove all the edges not in a certain spanning tree of \(H_i[C]\). Therefore, the situation is substantially the same as when \(H\) has at most \(2n-5\) edges.
If \(H_i[C]\) is a tree: Since there are \(|C|-1\) edges in the tree and the condition \(|C \cap V_i| \geq |C \cap V_1|\) holds, there must exist a vertex \(v \in C\) of color \(i\) which has degree at most \(1\). Then, \(v\) has degree at most \(1\) also in \(H\). However, for a bipartite planar graph \(H\) that has a vertex of degree at most \(1\), it can have at most \(2n-5\) edges when \(n \geq 4\).
Therefore, both cases turn out to be disadvantageous for creating a situation where no Kempe change can improve the coloring, and intuitively, for this reason, creating such a situation is impossible when \(|V_1| \geq n/2\) (we prove this in 4 in a way that analyzes “excessive edges” and “low-degree vertices”). As a result, by repeatedly applying Kempe changes while \(|V_1| \geq n/2\), we can obtain a \(4\)-coloring such that each color is used on fewer than \(n/2\) vertices.
4 The Proof and Algorithm↩︎
Now, we start proving the main technical theorem for a general number of colors \(k\) and a generalized graph class parameterized by \(\alpha \geq -4\). Note that we use \(\alpha = -4\) for planar graphs, by 1.
Theorem 2 (restated). Let \(\alpha \geq -4\) be a constant parameter and \(k \geq 3\). Let \(G\) be a \(k\)-colorable graph of \(n \geq 3\) vertices, such that for all its bipartite subgraphs \(H\) with 3 or more vertices, \(|E(H)| \leq 2 |V(H)| + \alpha\) holds. Given \(G = (V, E)\) together with a \(k\)-coloring \(\varphi: V \to \{1, \dots, k\}\), one can compute a \(k\)-coloring of \(G\) such that each color is used on at most \(\left\lceil \frac{n+\alpha+2}{k-2} \right\rceil\) vertices, in \(O(kn \log n)\) time.
4.1 Part 1: Analysis of Components↩︎
In this section, before proceeding to the explanation of our algorithm, we formulate the conditions of connected components in the graph stated in 1.
4.1.0.1 The Setup.
For the given \(k\)-coloring \(\varphi : V \to \{1, \dots, k\}\), let \(V_i := \{v \in V : \varphi(v) = i\}\) for \(i = 1, \dots, k\). If \(\varphi\) does not yet meet the output condition, we can assume w.l.o.g. that \(|V_1| > \left\lceil \frac{n+\alpha+2}{k-2} \right\rceil\).
As described in 3, we define the graph \(H_i := G[V_1 \cup V_i]\) for \(i = 2, \dots, k\) and \(H := H_2 \cup \dots \cup H_k\). We analyze the structure of each \(H_i\). For each \(i = 2, \dots, k\), let \(C_{i,1}, \dots, C_{i,q_i} \subseteq V(H_i)\) be the components of \(H_i\), where \(q_i\) is the number of components. For each component \(C_{i,j}\), we define the values \(a_{i,j}, b_{i,j}, e_{i,j}, p_{i,j}\) as in 1.
| Value | Definition | Meaning |
|---|---|---|
| \(a_{i, j}\) | \(= |C_{i,j} \cap V_1|\) | Number of vertices with color \(1\) |
| \(b_{i, j}\) | \(= |C_{i,j} \cap V_i|\) | Number of vertices with color \(i\) |
| \(e_{i, j}\) | \(= |E(G[C_{i,j}])|\) | Number of edges |
| \(p_{i, j}\) | \(= \sum_{v \in C_{i,j} \cap V_i} \max(2 - d_{H_i}(v), 0)\) | The “penalty” for low-degree color \(i\) vertices |
The key factor in deciding whether we can improve the coloring \(\varphi\) lies in \(a_{i,j} - b_{i,j}\). This is because, if we apply Kempe change in the component \(C_{i,j}\), the number of vertices of colors \(1\) and \(i\) decreases and increases by \(a_{i,j} - b_{i,j}\), respectively. Therefore, the goal of this section is to derive some useful conditions on the distribution of \(a_{i,j} - b_{i,j}\).
Lemma 1. \(|E(H)| \leq (2n+\alpha) - \sum_{v \in V_2 \cup \dots \cup V_k} \max(2 - d_H(v), 0)\).
Proof. First, by \(\alpha \geq -4\) and \(n \geq 3\), we have \(|V_1| > \left\lceil \frac{n+\alpha+2}{k-2} \right\rceil \geq \left\lceil \frac{1}{k-2} \right\rceil \geq 1\). Thus, \(|V_1| \geq 2\) holds. Next, let \(S = \{v \in V_2 \cup \dots \cup V_k : d_H(v) < 2\}\). Then, since \(H\) is a bipartite graph that can be divided into two parts \(V_1\) and \(V_2 \cup \dots \cup V_k\), we have \(|E(H)| = |E(H[V \setminus S])| + \sum_{v \in S} d_H(v)\). Here:
\(|E(H[V \setminus S])| \leq 2 |V \setminus S| + \alpha\) holds. This is because, if \(|V \setminus S| \geq 3\) then the inequality holds by assumption, and otherwise, since \(|V_1| \geq 2\), the only possibility is that \(V \setminus S = V_1\) and \(|V_1| = 2\), and in this case, \(|E(H[V \setminus S])| = 0 \leq 2 |V \setminus S| + \alpha\) due to \(\alpha \geq -4\).
Also, we have \(\sum_{v \in S} d_H(v) = \sum_{v \in S} \{2 - (2 - d_H(v))\} = 2 |S| - \sum_{v \in S} (2 - d_H(v))\).
Summing up these two results, we have \(|E(H)| \leq (2 |V \setminus S| + \alpha) + \{2 |S| - \sum_{v \in S} (2 - d_H(v))\} = 2n + \alpha - \sum_{v \in V_2 \cup \dots \cup V_k} \max(2 - d_H(v), 0)\). ◻
Lemma 2. \(\sum_{i=2}^k \sum_{j=1}^{q_i} (e_{i,j} + p_{i,j}) \leq 2n+\alpha\).
Proof. We rewrite the result of 1 using \(e_{i,j}\) and \(p_{i,j}\). First, \(|E(H)| = \sum_{i=2}^k \sum_{j=1}^{q_i} e_{i,j}\) holds by definition of \(H\). Also, for \(i \in \{2, \dots, k\}\), observe that \(d_H(v) = d_{H_i}(v)\) holds for each \(v \in V_i\). Then, \[\sum_{v \in V_2 \cup \dots \cup V_k} \max(2 - d_H(v), 0) = \sum_{i=2}^k \sum_{j=1}^{q_i} \sum_{v \in C_{i,j} \cap V_i} \max(2 - d_{H_i}(v), 0) = \sum_{i=2}^k \sum_{j=1}^{q_i} p_{i,j}\] and therefore, from 1, we obtain \(\sum_{i=2}^k \sum_{j=1}^{q_i} e_{i,j} \leq 2n+\alpha - \sum_{i=2}^k \sum_{j=1}^{q_i} p_{i,j}\). ◻
Lemma 3. \(e_{i,j} + p_{i,j} \geq \max(a_{i,j}+b_{i,j}-1, 2b_{i,j})\).
Proof. It suffices to prove that \(e_{i,j}+p_{i,j} \geq a_{i,j}+b_{i,j}-1\) and \(e_{i,j}+p_{i,j} \geq 2b_{i,j}\).
Since \(H_i[C_{i,j}]\) is connected, \(e_{i,j} \geq |C_{i,j}|-1 = a_{i,j} + b_{i,j} - 1\). As \(p_{i,j} \geq 0\) is obvious, we have \(e_{i,j} + p_{i,j} \geq a_{i,j} + b_{i,j} - 1\).
Also, \(e_{i,j} + p_{i,j} = \sum_{v \in C_{i,j} \cap V_i} d_{H_i}(v) + \sum_{v \in C_{i,j} \cap V_i} \max(2 - d_{H_i}(v), 0) = \sum_{v \in C_{i,j} \cap V_i} \max(d_{H_i}(v), 2) \geq 2 |C_{i,j} \cap V_i| = 2b_{i,j}\).
◻
Lemma 4. \(\sum_{i=2}^k \sum_{j=1}^{q_i} (a_{i,j}+b_{i,j}) = (k-2)|V_1|+n\).
Proof. By definition, \(\sum_{j=1}^{q_i} a_{i,j} = |V_1|\) and \(\sum_{j=1}^{q_i} b_{i,j} = |V_i|\). Therefore,
\[\begin{align} \sum_{i=2}^k \sum_{j=1}^{q_i} (a_{i,j}+b_{i,j}) = \sum_{i=2}^k (|V_1| + |V_i|) &= (k-2) |V_1| + (|V_1| + \dots + |V_k|) \\ &= (k-2) |V_1| + n. \qedhere \end{align}\] ◻
Lemma 5. \(\sum_{i=2}^k \sum_{j=1}^{q_i} \max(b_{i,j}-a_{i,j}, -1) \leq -(k-2) |V_1| + (n+\alpha)\).
Proof. We obtain \(\max(b_{i,j}-a_{i,j}, -1) \leq (e_{i,j}+p_{i,j}) - (a_{i,j}+b_{i,j})\) by subtracting \(a_{i,j}+b_{i,j}\) from both sides of the inequality in 3. Therefore: \[\begin{align} \sum_{i=2}^k \sum_{j=1}^{q_i} \max(b_{i,j}-a_{i,j}, -1) &\leq& \sum_{i=2}^k \sum_{j=1}^{q_i} (e_{i,j}+p_{i,j}) - \sum_{i=2}^k \sum_{j=1}^{q_i} (a_{i,j}+b_{i,j}) \\ &\leq& (2n+\alpha) - \{(k-2)|V_1|+n\} \end{align}\] where the last inequality is due to 2 and 4. Note that \((2n+\alpha) - \{(k-2)|V_1|+n\} = -(k-2) |V_1| + (n+\alpha)\). ◻
The implication of 5 is that the larger \(|V_1|\) is, the more components \(C_{i,j}\) such that \(a_{i,j} > b_{i,j}\) there are. Especially, given that \(|V_1| > \left\lceil \frac{n+\alpha+2}{k-2} \right\rceil\) (which implies \(|V_1| \geq \frac{n+\alpha+2}{k-2} + 1\)), 5 states that \(\sum_{i=2}^k \sum_{j=1}^{q_i} \max(b_{i,j}-a_{i,j}, -1) \leq -k\). This means that \(\sum_{j=1}^{q_i} \max(b_{i,j}-a_{i,j}, -1) \leq -2\) for some \(i\), and hence \(H_i\) has at least two components.
4.2 Part 2: The Algorithm↩︎
In this section, we derive a fast algorithm to obtain a \(k\)-coloring that is balanced enough. The strategy is to repeat the steps that make the coloring \(\varphi\) more balanced, using Kempe changes.
For a subset \(S \subseteq \{1, \dots, q_i\}\), if we apply Kempe changes to all \(C_{i,j}\) such that \(j \in S\), then the number of vertices of color \(1\) becomes \(|V_1| - \sum_{j \in S} (a_{i,j}-b_{i,j})\), and the number of vertices of color \(i\) becomes \(|V_i| + \sum_{j \in S} (a_{i,j}-b_{i,j})\). From now on, we discuss whether it is possible to choose a subset \(S \subseteq \{1, \dots, q_i\}\) on which to apply Kempe changes, so that the coloring \(\varphi\) improves.
We define \(\delta := |V_1| - \left(\frac{n+\alpha+1}{k-2}+1\right)\) to express how excessive the number of vertices of color \(1\) is compared to the threshold; e.g., \(\delta = \frac{1}{k-2}\) when \(|V_1| = \frac{n+\alpha+2}{k-2}+1\) (the case with minimum \(|V_1|\)).
Lemma 6. There exists some \(i\) such that \(\sum_{j=1}^{q_i} \max(b_{i,j}-a_{i,j}, -1) \leq -\left(\frac{1}{2} \delta + 1\right)\).
Proof. By 5, there exists some \(i\) such that
\[\sum_{j=1}^{q_i} \max(b_{i,j}-a_{i,j}, -1) \leq \frac{-(k-2)|V_1|+(n+\alpha)}{k-1} = -\left(\frac{k-2}{k-1} \delta +1\right) \leq -\left(\frac{1}{2} \delta + 1\right)\]
where the final inequality is due to \(k \geq 3\). ◻
Lemma 7. For \(i \in \{2, \dots, k\}\) and \(x > 0\), if \(\sum_{j=1}^{q_i} \max(b_{i,j}-a_{i,j}, -1) \leq -x\), then the following holds:
\(|V_1| > |V_i|\).
\(a_{i,j} - b_{i,j} \leq (|V_1|-|V_i|)-(x-1)\) for all \(j \in \{1, \dots, q_i\}\).
Proof. First, \(|V_1| = \sum_{j=1}^{q_i} a_{i,j}\) and \(|V_i| = \sum_{j=1}^{q_i} b_{i,j}\) by definition; (a) is shown by: \[|V_i| - |V_1| = \sum_{j=1}^{q_i} (b_{i,j}-a_{i,j}) \leq \sum_{j=1}^{q_i} \max(b_{i,j}-a_{i,j}, -1) \leq -x < 0\] It remains to prove (b). By assumption, we have: \[\sum_{j=1}^{q_i} \{\max(b_{i,j}-a_{i,j}, -1) - (b_{i,j}-a_{i,j})\} \leq -x - (|V_i|-|V_1|) = (|V_1|-|V_i|) - x\] Since \(\max(b_{i,j}-a_{i,j}, -1) - (b_{i,j}-a_{i,j})\) is non-negative for all \(j\), \(\max(b_{i,j}-a_{i,j}, -1) - (b_{i,j}-a_{i,j}) \leq (|V_1| - |V_i|) - x\) must hold for all \(j\). Therefore, \((-1) - (b_{i,j}-a_{i,j}) \leq (|V_1| - |V_i|) - x\) also holds, which means that \(a_{i,j}-b_{i,j} \leq (|V_1|-|V_i|)-(x-1)\). This proves (b). ◻
Lemma 8. Let \(s, t\) be real numbers such that \(s > t \geq 0\). Let \(d_1, \dots, d_m\) be (not necessarily non-negative) real numbers. If \(d_1 + \dots + d_m = s\) and \(d_1, \dots, d_m \leq t\), then there exists a subset \(S \subseteq \{1, \dots, m\}\) such that \(\frac{s-t}{2} \leq \sum_{i \in S} d_i \leq \frac{s+t}{2}\).
Proof. Let \(f(i) = d_1 + \dots + d_i \;(i \in \{0, \dots, m\})\). Then, there exists \(i \in \{1, \dots, m\}\) such that \(f(i-1) < \frac{s-t}{2}\) and \(f(i) \geq \frac{s-t}{2}\). This is because \(f(0) = 0 < \frac{s-t}{2}\) and \(f(m) = s \geq \frac{s-t}{2}\). For such \(i\), we have \(f(i) = f(i-1)+d_i < \frac{s-t}{2} + t = \frac{s+t}{2}\). Therefore, by choosing \(S = \{1, \dots, i\}\), we have \(\frac{s-t}{2} \leq \sum_{i \in S} d_i \leq \frac{s+t}{2}\). ◻
Lemma 9. For \(i \in \{2, \dots, k\}\) and \(x > 1\), if \(\sum_{j=1}^{q_i} \max(b_{i,j}-a_{i,j}, -1) \leq -x\), then there exists a subset \(S \subseteq \{1, \dots, q_i\}\) such that \(\frac{x-1}{2} \leq \sum_{j \in S} (a_{i,j}-b_{i,j}) \leq (|V_1|-|V_i|) - \frac{x-1}{2}\).
Proof. Because of 7, we can apply 8 with \(m := q_i, d_j := a_{i,j}-b_{i,j}\), and \(s = |V_1|-|V_i|, t = (|V_1|-|V_i|)-(x-1)\). Note that \(t \geq 0\) holds because otherwise \(d_1, \dots, d_m \leq t < 0\) and \(d_1 + \dots + d_m = s > 0\) would contradict. The consequence is that there exists a subset \(S \subseteq \{1, \dots, q_i\}\) such that \(\frac{s-t}{2} \leq \sum_{j \in S} (a_{i,j}-b_{i,j}) \leq \frac{s+t}{2}\). Here, \(\frac{s-t}{2} = \frac{x-1}{2}\) and \(\frac{s+t}{2} = (|V_1|-|V_i|) - \frac{x-1}{2}\). ◻
Lemma 10. For some \(i\), there exists a subset \(S \subseteq \{1, \dots, q_i\}\) such that \(\frac{1}{4} \delta \leq \sum_{j \in S} (a_{i,j}-b_{i,j}) \leq (|V_1|-|V_i|) - \frac{1}{4} \delta\).
Proof. By 6, there exists some \(i\) such that \(\sum_{j=1}^{q_i} \max(b_{i,j} - a_{i,j}, -1) \leq -\left(\frac{1}{2} \delta + 1\right)\). By assigning \(x = \frac{1}{2} \delta + 1\) to 9, we obtain the following: there exists a subset \(S \subseteq \{1, \dots, q_i\}\) such that \[\frac{1}{4}\delta \leq \sum_{j\in S}(a_{i,j}-b_{i,j}) \leq (|V_1|-|V_i|)-\frac{1}{4}\delta \qedhere\] ◻
The implication of 10 is that the more unbalanced the coloring \(\varphi\) is, the more improvement we can make in one batch of Kempe changes. Based on these lemmas, we can construct an algorithm to find a sufficiently balanced coloring. The algorithm is formally given in 5.
4.3 Part 3: Analysis of Time Complexity↩︎
Lemma 11. In 5, at most \(k \cdot \lceil \log_{4/3} (nk) \rceil\) loops will occur.
Proof. We observe that, after processing line 6 of 5, \(|V_1|\) and \(|V_i|\) both become at most \(|V_1| - \frac{1}{4} \delta\). Therefore, \(\delta\) is non-increasing throughout all loops.
Let \(\delta_0\) be the current \(\delta\). We consider a moment after that where \(\delta > \frac{3}{4} \delta_0\). Note that \(\delta \leq \delta_0\) by the observation above. After processing line 6 for this loop, \(|V_1|\) and \(|V_i|\) both become at most \[|V_1| - \frac{1}{4} \delta = \frac{3}{4} \delta + \left(\frac{n+\alpha+1}{k-2}+1\right) \leq \frac{3}{4} \delta_0 + \left(\frac{n+\alpha+1}{k-2}+1\right)\] by definition of \(\delta\). Therefore, the number of \(i\)’s that \(|V_i| > \frac{3}{4} \delta_0 + \left(\frac{n+\alpha+1}{k-2}+1\right)\) will decrease and eventually becomes zero after at most \(k\) loops. This means that, after \(k\) loops, \(\delta\) will be at most \(\frac{3}{4}\) times its original value.
Since \(\delta < n\) at the beginning, \(\delta\) becomes less than \(\frac{1}{k}\) after \(k \cdot \lceil \log_{4/3} (nk) \rceil\) loops. However, while \(|V_1| > \left\lceil \frac{n+\alpha+2}{k-2} \right\rceil\), we have \(\delta \geq \frac{1}{k}\). Therefore, at most \(k \cdot \lceil \log_{4/3} (nk) \rceil\) loops will occur. ◻
Finally, we show that we can compute a \(k\)-coloring of \(G\) such that each color is used in at most \(\left\lceil \frac{n+\alpha+2}{k-2} \right\rceil\) vertices, in \(O(kn \log n)\) time, which proves 1.
Lemma 12. \(|E(G)| \leq 4n+2\alpha\).
Proof. If we choose \(S \subseteq V\) uniformly at random (out of \(2^n\) possible choices), the edges between \(S\) and \(V \setminus S\) form a bipartite subgraph. By assumption, the number of edges in this subgraph is at most \(2n + \alpha\). However, since each edge is chosen with probability \(\frac{1}{2}\), the expected number of edges is \(\frac{1}{2} |E(G)|\). Therefore, \(\frac{1}{2} |E(G)| \leq 2n+\alpha\), which means that \(|E(G)| \leq 4n+2\alpha\). ◻
Lemma 13. Each loop of 5 can be executed in \(O(n)\) time.
Proof. We first discuss the required time complexity to find \(i\) such that \(\sum_{j=1}^{q_i} \max(b_{i,j}-a_{i,j}, -1)\). The naive implementation that computes all components \(C_{i,j}\) with depth-first search (DFS) takes \(O(|V(H_i)| + |E(H_i)|)\) time; summing over all \(i = 2, \dots, k\) could yield a total time of \(\Theta(kn)\) if \(|V_1|\) is large. However, it is enough to enumerate all components except isolated vertices; then, at most \(2 |E(H_i)|\) vertices are concerned, so the time complexity for DFS becomes only \(O(|E(H_i)|)\). For the isolated vertices, we only need to count the unvisited vertices in \(V_1\) and \(V_i\) and add their contribution to the result \(\sum_{j=1}^{q_i} \max(b_{i,j}-a_{i,j}, -1)\); this only takes \(O(1)\) time. Therefore, the total time to process line 4 in 5 is \(O(\sum_{i=2}^k |E(H_i)|) = O(|E(H)|) = O(n)\), due to \(|E(H)| \leq 2n + \alpha\).
For the remaining procedure, it takes \(O(|V(G)|)\) time to rearrange colors, \(O(|E(G)|)\) time to find all edges from vertices of color \(1\), and \(O(|V(H_i)| + |E(H_i)|)\) time for lines 5 and 6 in 5. Here, since \(|E(G)| \leq 4n+2\alpha\) (12) and \(|E(H_i)| \leq 2n+\alpha\), it takes \(O(n)\) time in total. ◻
Proof of 1. In 5, each loop is executed in \(O(n)\) time (13) and only \(O(k \log n)\) loops will occur (11; note that we can assume \(k \leq n\) since the \(k > n\) case is trivial). Therefore, 5 terminates in \(O(kn \log n)\) time. Also, due to the loop termination condition, 5 correctly computes a coloring \(\varphi\) such that each color is used on at most \(\left\lceil \frac{n+\alpha+2}{k-2} \right\rceil\) vertices. ◻
5 Consequences↩︎
In this section, we discuss the consequences of 1 for planar graphs and other surfaces.
5.1 Planar Graphs↩︎
Every bipartite planar graph with \(n \geq 3\) vertices has at most \(2n-4\) edges (1). Hence, for a planar graph \(G\), all its bipartite subgraphs \(H\) with \(|V(H)| \geq 3\) satisfy \(|E(H)| \leq 2 |V(H)| - 4\). Therefore, we can use 1 with \(\alpha = -4\). Moreover, by the four-color theorem [1], the planar graph \(G\) is guaranteed to be \(k\)-colorable for \(k \geq 4\), and the recent result by [3] shows that a \(4\)-coloring of \(G\) can be computed in \(O(n \log n)\) time. Therefore, the following result holds:
Corollary 1. For \(k \geq 4\), every planar graph with \(n \geq 3\) vertices admits a \(k\)-coloring such that each color is used on at most \(\left\lceil \frac{n-2}{k-2} \right\rceil\) vertices, and such a coloring can be computed in \(O(kn \log n)\) time.
This bound exactly matches the lower bound of \(\left\lceil \frac{n-2}{k-2} \right\rceil\), achieved with a planar graph \(K_{1,1,n-2}\) (1). In particular, for \(k = 4\), every planar graph with \(n \geq 3\) vertices admits a 4-coloring such that each color is used on fewer than half of the vertices, and such a coloring can be computed in \(O(n \log n)\) time. This is itself stronger than the four-color theorem.
5.2 Results for Other Surfaces↩︎
The result can also be applied to general surfaces, e.g., the torus and the projective plane. For a surface, the Euler characteristic \(\chi\) is defined, where every connected graph \(G = (V, E)\) embedded on this surface satisfies \(|V| - |E| + |F| \geq \chi\), with \(F\) denoting the set of faces. For example, \(\chi = 2\) for the plane, \(\chi = 1\) for the projective plane, and \(\chi = 0\) for the torus and the Klein bottle.
Proposition 3 ([24]). Every bipartite graph with \(n \geq 3\) vertices on a connected surface with Euler characteristic \(\chi\) has at most \(2n-2\chi\) edges.
By 3, we can use 1 with \(\alpha = -2\chi\); since \(\chi \leq 2\) holds for every connected surface, the assumption \(\alpha \geq -4\) is automatically satisfied. Then, we obtain the following result. In particular, for a closed orientable surface, its Euler characteristic is expressed as \(\chi = 2 - 2g\) where \(g\) is its genus, meaning the threshold in the corollary below becomes \(\left\lceil \frac{n+4g-2}{k-2} \right\rceil\) in this case.
Corollary 2. For \(k \geq 3\), given a graph with \(n \geq 3\) vertices on a fixed connected surface with Euler characteristic \(\chi\), together with its \(k\)-coloring \(\varphi: V \to \{1, \dots, k\}\), one can obtain a \(k\)-coloring such that each color is used on at most \(\left\lceil \frac{n-2\chi+2}{k-2} \right\rceil\) vertices, in \(O(kn \log n)\) time.
Finally, we note that the result above holds beyond the surface’s colorability. For example, it is proved that every graph on the torus is \(7\)-colorable [25], but if \(G\) is \(4\)-colorable, then there exists a \(4\)-coloring such that each color is used on at most \(\left\lceil \frac{n+2}{2} \right\rceil\) vertices.
6 Conclusion↩︎
In this paper, we showed that every planar graph with three or more vertices admits a \(4\)-coloring in which no color is used on half or more of the vertices. This result is shown in the form of 1, which allows us to generalize to five or more colors and other surfaces. We consider that our result is particularly meaningful when the number of colors \(k\) is small. This is because, if \(k\) is large enough, the following reduction works:
If a given \(\varphi\) is a coloring where each color is used on at most \(\left\lceil \frac{n+\alpha+2}{k-2} \right\rceil\) vertices, just output \(\varphi\).
Otherwise, one can obtain an independent set \(S \subseteq V\) of size exactly \(\left\lceil \frac{n+\alpha+2}{k-2} \right\rceil\) from the largest color class in \(\varphi\), and then it remains to find a \((k-1)\)-coloring of \(G[V \setminus S]\) where each color is used on at most \(\left\lceil \frac{n+\alpha+2}{k-2} \right\rceil\) vertices.
This reduction applies only if \(G[V \setminus S]\) is \((k-1)\)-colorable and its initial \((k-1)\)-coloring can be computed efficiently. This is true when \(k \geq 5\) for planar graphs, due to an \(O(n \log n)\)-time algorithm to find a \(4\)-coloring of planar graphs [3]. Therefore, \(k = 4\) is the essentially important case for planar graphs. Likewise, for general graphs that meet the condition of 1, they are typically \(9\)-degenerate by 12, and such graphs are \(10\)-colorable in polynomial time. For these reasons, the essential cases are when \(k\) is small, e.g., \(k \leq 10\).
Finally, we believe that this paper has some implications beyond this result. First, while the four-color theorem is notoriously complex, one can obtain a meaningful generalization by treating it as a “black box.” Second, while Kempe chains have often been used for induction (for the four-color theorem) or for reconfiguration problems, they can also be used as an optimization algorithm in graph coloring. We conclude this paper by posing the following conjectures:
Conjecture 1. Given a planar graph with \(n \geq 3\) vertices, one can compute a 4-coloring in which each color is used on fewer than \(n/2\) vertices in \(O(n)\) time.
Conjecture 2. Every triangle-free planar graph with \(n \geq 2\) vertices admits a 3-coloring in which each color is used on at most \(n/2\) vertices (a possible extension of Grötzsch’s theorem [26]).
Particularly for 2, the example in 2 that uses the Grötzsch graph (as a \(4\)-critical graph) is an important graph that every \(3\)-coloring has a color that is used on at least \(n-10\) vertices. This graph can be embedded in a projective plane, which implies that the conjecture would likely not hold for surfaces other than the plane.
Acknowledgments↩︎
The authors thank Yuta Inoue, Atsuyuki Miyashita, and Tonan Kamata for helpful discussions, and Akihito Yoneyama for helpful suggestions to improve this paper.