# A Linear-Time Algorithm for 4-Coloring Some Classes of Planar Graphs

Authors: Zuosong Liang; Huandi Wei
Journal: Computational Intelligence and Neuroscience
 (2021)

---

## Abstract

Every graphG=V,E considered in this paper consists of a finite set V of vertices and a finite set E of edges, together with an incidence function that associates each edge e∈E of G with an unordered pair of vertices of G which are called the ends of the edge e. A graph is said to be a planar graph if it can be drawn in the plane so that its edges intersect only at their ends. A proper k-vertex-coloring of a graph G=V,E is a mapping c:V⟶S (S is a set of k colors) such that no two adjacent vertices are assigned the same colors. The famous Four Color Theorem states that a planar graph has a proper vertex-coloring with four colors. However, the current known proof for the Four Color Theorem is computer assisted. In addition, the correctness of the proof is still lengthy and complicated. In 2010, a simple On2 time algorithm was provided to 4-color a 3-colorable planar graph. In this paper, we give an improved linear-time algorithm to either output a proper 4-coloring of G or conclude that G is not 3-colorable when an arbitrary planar graph G is given. Using this algorithm, we can get the proper 4-colorings of 3-colorable planar graphs, planar graphs with maximum degree at most five, and claw-free planar graphs.


---

## Body

## 1. Introduction

EverygraphG=V,E considered here consists of a finite set V of vertices and a finite set E of edges, together with an incidence function that associates each edge of G with an unordered pair of vertices of G. If u,v is the unordered pair of vertices corresponding to the edge e of G, then e is denoted by e=uv and u is said to be adjacent to v. In addition, if e=uv, e is said to be incident to u and v and u and v are called the ends of e. For the standard terminology not given here, we refer the reader to [1]. The number of vertices of G is called the order of G. For a vertex v∈V, the open neighborhoodNv of v is defined as the set of vertices adjacent to v. The closed neighborhoodNv of v is defined as Nv=Nv∪v. The degree of v is equal to Nv, denoted by dGv or simply dv. By δG and ΔG, we denote the minimum degree and the maximum degree of graph G, respectively. A k-regular graphG is a graph such that every vertex of G has the degree k. For a subset S⊆V, the induced subgraph, denoted by GS, is the subgraph of G whose vertex set is S and whose edge set consists of all edges of G which have both ends in S. A complete graph is a simple graph in which any two vertices are adjacent. Let Kn denote the complete graph on n vertices. Usually, K3 is called a triangle. A cycle on three or more vertices is a simple graph whose vertices can be arranged in a cyclic sequence in such a way that two vertices are adjacent if they are consecutive in the sequence and are nonadjacent otherwise. A graph G is bipartite if its vertex set can be partitioned into two sets V1 and V2 so that every edge has one end in V1 and the other one in V2. Specially, if every vertex in V1 is adjacent to every vertex in V2, then G is called a complete bipartite graph. As usual, Km,n denotes a complete bipartite graph with classes of cardinality m and n. The graph K1,3 is also called a claw. Given a graph F, a graph G is F-free if it does not contain F as an induced subgraph. In particular, a K1,3-free graph is claw-free. By starting with a disjoint union of two graphs G and H and adding edges joining every vertex of G to every vertex of H, one obtains the join of G and H, denoted by G∨H. The join Cn∨K1 of a cycle Cn and a single vertex is referred to as a n-wheel denoted by Wn.A graph is said to be aplanar graph if it can be drawn in the plane so that its edges intersect only at their ends. Such a drawing is called a planar embedding of the graph. Any such particular embedding is called a plane graph. A proper k-vertex-coloring, or simply a properk-coloring, of a graph G=V,E is a mapping c:V⟶S (S is a set of k colors) such that no two adjacent vertices are assigned the same colors. In this paper, we refer to a proper coloring as a “coloring” and to a proper k-coloring as a “k-coloring.” The famous Four Color Theorem states that a planar graph has a proper coloring with four colors. The original proof of the Four Color Theorem by Appel and Haken [2] and Appel et al. [3] relies heavily on the computer for checking details involved in finding an unavoidable set and verifying that all configurations in that set are reducible. It employs no fewer than 487 discharging rules, resulting in a set of over 1400 unavoidable configurations. The more recent proof by Robertson et al. [4], although also dependent on the computer, is simpler in many ways. In their proof, thirty-two discharging rules are needed, generating a list of 633 unavoidable configurations.In 2010, a simpleOn2 time algorithm is provided to 4-color a 3-colorable planar graph by Kawarabayashi and Ozeki [5]. In this paper, given a planar graph G, we design an improved linear-time algorithm to either output a 4-coloring of G or conclude that G is not 3-colorable. Using this algorithm, we can get the 4-colorings of 3-colorable planar graphs, planar graphs with maximum degree at most five, and claw-free planar graphs.


## 2. Proof and Algorithm

First, we give some definitions and lemmas which are related to our algorithm. A plane graphG partitions the plane into a number of arcwise-connected open sets which are called the faces of G. We call f a k-face if f is incident to k edges of G. For a simple plane graph G, we call a vertex v of degree five bad if all faces incident with v, except for the at most one, are triangles and the exceptional face has size at most five. Moreover, v is Type I, Type II, and Type III if the exceptional face is a triangle, a 4-face and a 5-face, respectively, as shown in Figure 1. Obviously, if a plane G has a bad vertex of Type I, then G is not 3-colorable. Note that, if v is a bad vertex of Type I of the plane graph, the induced subgraph GNv is not necessarily a 5-wheel since GNv may have a triangle and thus GNv has a K4. To identify nonadjacent vertices x and y of a graph G is to replace the two vertices by a single vertex incident to all the edges which are incident to either x or y. About the bad vertex v of Type II or III, the following observation is obvious.Figure 1
A bad vertex.Observation 1.
Letv be a bad vertex of Type II or III of G (see Figure 1). Then, u1 and u2 are contained in the same color class for any 3-coloring of G. Let G′ be the graph obtained from G by identifying u1 and u2. Then, G is 3-colorable if and only if G′ is 3-colorable.The following lemmas are useful for our proofs.Lemma 2 (see [5]).
Every simple planar graphG contains (i) a vertex of degree at most 4 or (ii) a bad vertex.Lemma 3 (see [5]).
LetG be a plane graph with a 4-coloring c′, and let f be a face of size at least four. Take four vertices x1, x2, x3, and x4 (along clockwise order) in f. Then, G also has a 4-coloring such that at most three colors are used for x1, x2, x3, and x4. Moreover, given the graph G and the coloring c′, we can find such a 4-coloring of G in On time, where n=G.Lemma 4 (see [6]).
Ifv is a vertex of planar graph G and GNv is {claw, K4}-free, then dv≤5 and GNv is a 5-wheel if dv=5.Theicosahedron is the 5-regular planar graph in Figure 2. In order to give our algorithm, we first give a well known fact about planar graphs.Figure 2
The icosahedron.Observation 5.
The icosahedron is the unique 5-regular planar graphG such that, for every vertex v∈VG, the induced subgraph GNv is a 5-wheel.Further, we can prove the following theorem.Theorem 6.
LetG be a claw-free planar graph. If G is not the icosahedron, then G has a vertex of degree at most four.Proof.
LetG=V,E be a claw-free planar graph. If G has no vertex of degree at most four, then δG≥5. In the following, we just prove that G is the icosahedron. If G has no K4, by Lemma 4, every vertex v of G induces a 5-wheel of G. So, by Observation 5, G is the icosahedron. If not, let x1x2x3x4 be a K4 of G and assume that x1 is inside the triangle x2x3x4 in the embedding of G on the plane. Without losing of the generality, we may assume that there is no other K4 inside the triangle x2x3x4. Suppose not, we can continue to find another K4 inside the triangle x2x3x4 and consider the inner situation in this K4 until finding such a triangle since G is a finite graph. Note that dx1≥5. Assume that some neighbors of x1 are inside the triangle x1x2x3. Let G∗ be the plane graph induced by the vertices on and inside x1x2x3. We have the following claim.Claim 1.
For every vertexx inside x1x2x3, GNx=G∗Nx and GNx is isomorphic to a 5-wheel by Lemma 4 and the assumption that there is no K4 in G∗.
Take any vertexv in VG∗−x1,x2,x3. GNv is isomorphic to a 5-wheel by Claim 1. Let Cv=v1v2v3v4v5v1 be the cycle of 5-wheel GNv. Note that at least three neighbors of v are inside the triangle x1x2x3 since it is impossible that three neighbors of v are the vertices of the triangle x1x2x3. Without losing of the generality, we assume that v1, v2, and v3 are inside x1x2x3. Then, GNv1, GNv2, and GNv3 are isomorphic to the 5-wheel by Claim 1. Let Cv1=v2vv5v6v7v2 be the cycle of 5-wheel GNv1 and Cv2=v3vv1v7v8v3 be the cycle of 5-wheel GNv2 (see Figure 3). Further, let Cv3=v4vv2v8v9v4 be the cycle of 5-wheel GNv3 (see Figure 4). Note that v4 is not adjacent to v8 in Figure 4, without losing of the generality, assume that v4 is inside x1x2x3. Then, GNv4 is a 5-wheel, and we claim that neither v6 nor v7 is the fifth neighbor of v4. If v7 is the fifth neighbor of v4, by the fact that GNv4 is a 5-wheel, v5 is also adjacent to v7, a contradiction to the fact that GNv1 is a 5-wheel. If v6 is the fifth neighbor of v4, by the fact that GNv4 is a 5-wheel, v9 is also adjacent to v6. Then, no matter how we draw the two edges v4v6 and v9v6 in the plane, we can get a vertex of degree four by the claw-freeness, a contradiction. So, let Cv4=v5vv3v9v10v5 be the cycle of 5-wheel GNv4. By the claw-freeness, v10 is adjacent to v6. We claim that v5 is also inside x1x2x3, and thus GNv5 is a 5-wheel (see Figure 5). Suppose not, if v5=x1, x4,v5x1,v4,v1 would induce a claw, a contradiction. Consider the vertices in v6,v7,v8,v9,v10 in Figure 5. Without losing of the generality, assume that v10 is inside x1x2x3. Then, dG∗v10=5, and GNv10 is a 5-wheel. We can easily see that neither v7 nor v8 is the fifth neighbor of v10. So, let Cv10=v9v4v5v6v11v9 be the cycle of 5-wheel GNv10. Hence, v11v6,v11v9⊂EG∗ by the claw-freeness and both v6 and v9 are inside x1x2x3. Further, we have that v11v7,v11v8⊂EG∗ by the claw-freeness (see Figure 2). Further, by the claw-freeness, no one in v7,v8,v11 is in the set x1,x2,x3. Suppose not, if v11=x1, x4,v11x1,v6,v9 would induce a claw, a contradiction. Then, all the vertices inside the triangle x1x2x3 induce the icosahedron (see Figure 2), still a contradiction to the assumption that some neighbor of x1 is inside the triangle x1x2x3.
Immediately, we have the following corollary.Figure 3
GNv,v1,v2.Figure 4
GNv,v1,v2,v3.Figure 5
GNv,v1,v2,v3,v4,v5.Corollary 7.
The icosahedron is the unique 5-regular planar graph such that every vertex is a bad vertex of Type I.Proof.
LetG=V,E be a 5-regular planar graph such that every vertex is a bad vertex of Type I. Then, G is also a claw-free planar graph. By Theorem 6, G is the icosahedron.
Based on Observation1, Lemma 2, Lemma 3, Corollary 7, and Theorem 6, we design an algorithm as follows.Theorem 8.
Given a planar graphG, Algorithm 1 is a linear-time algorithm to output either a 4-coloring of G or the decision that G is not 3-colorable. In addition, if G is a 3-colorable planar graph or a planar graph with maximum degree at most five or a claw-free planar graph, Algorithm 1 gives a 4-coloring of G.Algorithm 1:An algorithm of coloring planar graphs.
Input. A planar graph G=V,E.Output. A 4-coloring of G or the decision that χG>3.Step 1. Give a partition VG=V1∪V2∪V3 such that the vertices in V1 have degree at most four and the vertices in V2 are bad vertices of Type II and III.Step 2. If the current graph is the icosahedron or have at most four vertices, we give a 4-coloring of G directly. If not, first take a vertex v in V1. Let G′=G−v and carry out AG′, turn to step 3. If there is no such a vertex, take a bad vertex v of Type II or III. Identifying u1 and u2 and denoting it by G′, then we carry out AG′, turn to step 5. If there is no such a vertex, stop the algorithm and output that χG>3.Step 3. If we get a 4-color of G′, turn to step 4. If we get that χG′>3, then stop the algorithm AG and output that χG>3.Step 4. Find a 4-color of G−v such that at most three colors are used in Nv (see Lemma 3). Give a 4-coloring of G. Stop the algorithm.Step 5. If we get a 4-color of G′, extend the coloring of G′ into a 4-coloring of G by assigning u1 and u2 the same color as in G′, stop the algorithm. If we get that χG′>3, then stop the algorithm AG and output that χG>3.Proof.
Based on Lemmas2 and 3 and the fact that identifying u1 and u2 in step 2 keeps the 3-colorability of G, we can say that Algorithm 1 outputs either a 4-coloring of G or the decision that G is not 3-colorable. Now, we prove that Algorithm 1 is a linear-time algorithm by induction on the order of G. Assume that it holds when the order of G is less than n. Then, let G=n. In step 1, we can find such a partition in at most On time. In step 2, we can give a 4-coloring of G directly in constant time if G is the icosahedron or has at most four vertices. If not, we can construct a graph G′ in constant time at most. Note that G′=n−1. By induction, AG′ needs On−1 time which is the total time of all repeated steps from 1 to 5 in AG′. In step 3, it needs only the constant time by deciding the result of AG′. In step 4, we can give a 4-coloring of G from the 4-coloring of G′ in On time by Lemma 3. In step 5, it needs only the constant time. Thus, the total time is also On.
IfG is a 3-colorable planar graph, we are sure to get a 4-coloring of G by Observation 1 and Lemmas 2 and 3. If G is a planar graph with maximum degree at most five, we just consider the case that a vertex of degree greater than five occurs in G′ by identifying u1 and u2 of G in step 2. When a vertex of degree greater than five occurs in G′, then v becomes a vertex of degree four of G′ (see Figure 1). According to our algorithm, we first take a vertex v of degree at most 4 in step 2 when we carry out AG′. Hence, after several steps, the vertex of degree greater than five will disappear. So, the final G′ will be the icosahedron or a graph with at most four vertices by Corollary 7, and we get a 4-coloring of G at last. If G is a claw-free planar graph, we can get a 4-coloring of G by Lemma 3 and Theorem 6.



---

*Source: 7667656-2021-10-05.xml*