{'fraction_non_alphanumeric': 0.04697786500385064, 'fraction_numerical': 0.01612302188656746, 'mean_word_length': 3.679065442287574, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 28, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A Unified Spiral Chain Coloring Algorithm for Planar Graphs

In this paper we have given a unified graph coloring algorithm for planar graphs. The problems that have been considered in this context respectively, are vertex, edge, total and entire colorings of the planar graphs. The main tool in the coloring algorithm is the use of spiral chain which has been used in the non-computer proof of the four color theorem in 2004. A more precies explanation of the proof of the four color theorem by spiral chain coloring is also given in this paper. Then we continue to spiral-chain coloring solutions by giving the proof of other famous conjectures of Vizing's total coloring and planar graph conjectures of maximum vertex degree six. We have also given the proof of a conjecture of Kronk and Mitchem that any plane graph of maximum degree"Delta"is entirely ("Delta"+4)-colorable.The last part of the paper deals with the three colorability of planar graphs under the spiral chain coloring. We have given an efficient and short proof of the Groetzsch's Theorem that triangle-free planar graphs are 3-colorable.


Introduction
Without doubt the root of all graph coloring problems e.g., see for example [13], [33] go to the famous four color map coloring problem of Guthrie [14] and its solution that is becoming a theorem has a long and strange story [1]- [3]. Also the lengthy and computer-aided proof(s) and verification of its correctness by another computer program makes the problem even more attractive and interesting [1], [17], [34].
The author has given an algorithmic proof to the four color theorem which is not rely on a computer program but it is based on graph theory notions such as vertices, edges, cycles, planar graphs etc., in 2004 [19]. The only new concept introduced in the proof, is a special path in the planar graph called spiral chain. By using spiral chains and spiral-chain coloring in the planar graphs proofs have been proposed for several open coloring problems [20], [21]. The purpose of this paper is to show that spiral chain coloring algorithm, for at least for planar graphs can be unified to other coloring problems. In order to show the ability of the spiral-chain coloring algorithm we have chosen maximal planar graphs for vertex, edge, total and entire coloring problems. Note that solutions of some of these problems are still open.
Throughout the paper let us assume that from a plane graph we understand a maximal planar graph embedded in the plane without crossing of the edges. The four color problem is to color the vertices of a plane graph with only four colors so that adjacent vertices receive different colors. The four color theorem says that four colors is enough for any plane graph. But the answer of the question of three colorability of the plane graph is open and only partial results exits, such as planar graphs without triangles or planar graphs with even triangulations have been shown to be 3-colorable [22], [23], [25]. We will be re-visited the spiral chain coloring solution of the Steinberg's three colorability problem in the last section of this paper for some extra justification [21], [24].
Probably edge-coloring of graphs is almost as old as the four color problem and comes from its equivalent formulation of Tait [6]. That is 4CT is equivalent to the coloring the edges of any cubic bridgeless planar graph with only three colors such that any two incident edges receive different colors. Again spiral chain edge coloring solution to this problem has been given by Cahit without relying on the proof of the four color theorem in 2005 [19]. The proof is based on the spiral chains of a bridgeless cubic graph and coloring them with three colors say Green, Yellow and Red, where Green has priority over Yellow and Red and Yellow has priority over color Red. Finally in case of color conflict at two incident edges use appropriate backward Kempe-chain switching to resolve the conflict [19]. Tait's coloring is the first example but the real starting point of edge coloring of graphs is the famous theorem of Vizing that states that any graph G has edge-chromatic number χ ′ (G) = ∆(G) or ∆(G) + 1, where ∆(G) is the maximum vertex degree in G and by "chromatic number" we mean minimum number of colors. The main problem in edge coloring is to determine which of these two possibilities holds for a given graph G. The graph G is called it is in Class I if χ ′ (G) = ∆(G) and is in Class II otherwise. It is a famous conjecture of Vizing that planar graphs with ∆(G) ≥ 6 are in Class I [16]. Except the case ∆(G) = 6 all other cases have been settled [32].
The problem of simultaneously coloring sets of elements of a graph posed by Ringel in 1960 [30] who conjectured that the vertices and faces of a plane graph may be colored with six colors. This has been settled by Borodin in [29]. Vizing conjectured that the vertices and edges of any graph may be colored with ∆(G) + 2 colors (known as total coloring of graphs) [10]. Similarly a conjecture of Melnikov for edge-face coloring has been settled by Sanders and Zhao [31].
Lastly plane graph coloring can be considered in its most general forum as coloring all elements (vertices, edges and faces) simultaneously. This type coloring has been considered under the name "entire coloring" by Kronk and Mitchem in 1972 [16]. They also conjectured that any plane graph of maximum degree ∆ can be colored with ∆(G) + 4 colors and showed that this true for ∆(G) = 3. Other results on this conjecture are first by Borodin for ∆(G) ≥ 12 and then ∆(G) ≥ 7 and finally improved to ∆(G) ≥ 6 by using discharging and non-existence of an minimal counter example by Sanders and Zhao [18]. The cases ∆(G) ∈ {4, 5} remain undecided.
In this paper we have shown that all the above coloring problems of the plane graphs can be settled algorithmically by the use of spiral chain coloring technique.

Spiral Chains
Let G(V, E) be a plane graph with vertex set V and edge set E. Assume that d(v) ≥ 3 for v ∈ V . The outer-cycle C o0 of G is a cycle for which there is no edges of G remain outer-region of C o . Note that |V (C o )| = 3 and all faces are triangles since G is maximal planar.
We define spiral chain(s) S 1 of G as a (disjoint) path(s) with a topological property (we mean the spiral shape of the path) as follows. The path is a subpath of spiral chain S 1 , that is we select edges of C o0 starting from v a in clockwise direction till v c . Then we delete the vertices of P (v a , v c ) and obtain the subgraph G 1 of G which is triangulated but not necessarily maximal since its outer-cycle C o1 may have length greater 3.
} the connecting link-edge of the spiral sub-paths P 1 (v a , v c ) and P 2 (v d,i , v d,i−1 ). Similar above we trace other vertices of the subgraphs G 2 , G 3 , ..., G k and obtain spiral chain of G if n = |V (G)| = ∪ k i=1 |V (G i )| which can be expressed as |V (G i )| < n then this means that there is no link-edge connecting the last spiral sub-path of G k to the next one in G k+1 . In this case we choose the closest vertex u to the last vertex v of S 1 such that vu / ∈ E(G). In general two consecutive spiral chains S k and S k+1 is separated by an maximal outerplanar subgraph G k,k+1 such that vu / ∈ E(G), v ∈ S k , u ∈ S k+1 . Start the spiral chain S 2 from u as described above. Eventually we obtain vertex disjoint spiral chains S 1 , S 2 , ..., S p when all vertices of G have been visited. Hence in general we can write the set of spiral chains of G as Note that if p = 1 then S 1 is an Hamiltonian path of G and for p > 1 some of spiral chains may be a isolated vertex.
For a given graph G the set of S of spiral chains decompose G into nested vertex disjoint spiral chains. Any vertex can belong exactly one spiral chain.
Since G is maximal planar graph its faces must be triangles (cycle of length three). A face (triangle) in G can be in three types: α, β and γ−triangles. Definition 1. An triangle in G under the spiral decomposition S is called αtriangle if all its edges are non-spiral edges, β−triangle if exactly two of its edges are non-spiral edges and γ−triangle if only one of its edge is an non-spiral edge.
It is not difficult to see that for any spiral decomposition S there exits at least one γ-triangle but we can draw graphs without α-triangles. The proof of the first statement can be seen that there is a spiral subpath with a link-edge and a suitable non-spiral edge which form an maximal outerplanar subgraph of G. But any maximal outerplanar graph has a γ-triangle. In Figure 1 we have shown an maximal planar graph and its spiral chain with all β-triangles except with one γ-triangle (shown in grey in the figure).

Spiral chain coloring
In this section we apply spiral chain coloring algorithm to the some of the planar graph coloring problems which have not completely settled. We have particularly investigated the undecided cases of the corresponding conjectures on edge, total and entire coloring conjectures. Let us first give an complementary justification of the proof of the four color theorem based on spiral chains of the maximal planar graphs. Assume that G has no vertex degree smaller than 4. We will be denoting the colors in several ways e.g., by numbers 1,2,3,4,.. or by letters c 1 , c 2 , c 3 , c 4 , ... or by capital letters Red, Y ellow, Green, Blue, ....

Spiral Chain Vertex Coloring
Stockmeyer has shown that 3-colorability is N P -complete for planar graphs but we can decide whether the planar graph is 3-colorable by using spiral chain coloring. We call a graph G is almost three colorable (4-chromatic critical) if it is possible to color vertices such that only one vertex has to be colored by the fourth color. In Fig. 1 we have illustrate 3-coloring of an maximal planar graph by using spiral chain coloring. The graph satisfy even triangulation condition of Heawood, so it has to be 3-colorable but we don't need to know that beforehand. In Fig. 2 we have shown another example of spiral chain coloring which is almost 3-colorable in the sense that only once and on the last vertex of the spiral chain the fourth color is being used. If G and its spiral chain decomposition has no α-triangle then Figs.1-4 suggest the following lemma: Lemma 3. Any α-triangle free maximal planar graph can be 4-colorable by spiral chain coloring without Kempe-switch.
Let S 1 , S 2 , ..., S k be the set of spiral chains of G. Spiral chain coloring algorithm colors the vertices of S 1 , S 2 , ..., S k in reverse order. Let V (S k ) = {v 1 , v 2 , ..., v m } ,m ≤ n be the set of vertices of S k . Spiral segment S k,i of S k is the subset of vertices V (S k,i ) = {v 1 , v 2 , ..., v p } i , i = 1, 2, ..., r, p ≤ m ≤ n such that induced an maximal outerplanar subgraph, where p is the length of the spiral segment and it is maximum possible with respect to this property. We also call this the first maximal outerplanar subgraph induced by the spiral segment vertices as the "core of the spiral". That is spiral segment vertices of the core is V (S k,1 ) = {v 1 , v 2 , ..., v p } 1 . In Fig. 2 the core of the spiral is shown in gray color and the first spiral segment vertices colored by G, R, G, Y, G, Y, R, Y, R and it can easily be seen that if we take next vertex (colored by Y ) to the spiral segment the core is no longer an maximal outerplanar subgraph. The next spiral segment together with the previous spiral segment vertices forms another maximal outerplanar subgraph (in Fig. 2 We also say, for any three consecutive spiral segments S k,(i−1) , S k,i , S k,(i−1) of spiral chain S k , spiral segment S k(i−1) is a lower-spiral segment of S k,i and spiral segment S k(i+1) is an upper-spiral segment of S k,i .
In its most general form an maximal planar graph is decomposed into vertex disjoint spiral chains and each spiral chain is further decomposed, in a well defined fashion, into vertex disjoint spiral segments. Moreover spiral chains and spiral segments are in the form of an shelling structure (nested shells of triangulations). Next we will show that there is an simple and efficient coloring algorithm that colors the vertices of spiral from the inner spiral chain toward an outer spiral chain. Since the core spiral segment S k,1 always induce an maximal outerplanar subgraph of the graph we start coloring core spiral-segment vertices with only three colors, say green, red and yellow without any color conflict. Let us call to these three colors as Color Class I, Note that we have just three colored the first spiral segment (core) and since it is maximal outerplanar graph three-coloring with CC 1 = {G, R, Y } is unique.
• A β-triangle in the core spiral segment S k,1 . That is if start from the very first triangle of the spiral chain which must be an γ-or β-triangle all other triangles induced by the core vertices uniquely colored by the colors of CC 1 . Now consider next spiral segment S k,2 which upper-spiral segment with respect to the core segment S k,1 . We continue the coloring the vertices of S k,2 with the colors in CC 1 as long as there is no α-or γ-triangle in the previous core subgraph.
forms three β-triangles and force to use the new color B for the vertex v. If (uw) ∈ S k,2 such that (uv i ), (wv i ), (wv i+1 ) ∈ E(G) are the non-spiral edges and c(u) = Y then we color w as c(w) = B. Hence in these cases we switch to new three color class CC 2 = {R, Y, B} .
From the above three colors classes CC 1 = {G, R, Y } and CC 2 = {R, Y, B} we define safe colors as follows: The color green G ∈ CC 1 is a safe-color with respect to CC 2 since G / ∈ CC 2 and similarly the color blue B ∈ CC 2 is a safe-color with respect to CC 1 since B / ∈ CC 1 . Hence the red R and yellow Y are non-safe colors for both CC 1 and CC 2 . Now let if we would have no other triangle types (that is no α-triangles) in the spiral decomposition we would color without need of use of Kempe-switch all spiral segments with the alternating the two three color classes CC 1 and CC 2 .
Now consider the last vertex v l of the last spiral segment S k,r . If r the number of spiral segments is odd then color v l as c(v l ) = G and if r is even then color v l as c(v l ) = B. This completes the proof of the above lemma.  We need a definition of a special subgraph in the spiral chain decomposition of G.

Definition 2. Consider two consecutive spiral chains (or spiral segments)
That is the subgraph formed in this way is called the "sailing boat" and pictorially looks like a sailing boat in between two consecutive parallel spiral chains which consist of one γ-triangle and three β-triangles. In other words the sailing boat subgraph is a wheel with five vertices drawn in the plane like the shape of a sailing boat between two parallel spiral segments.
• An α-triangle in the core spiral segment S k,1 . It is easy to see that under spiral chains decomposition an isolate α-triangle can create three γtriangles. That is in an triangulation under spiral chain, any sequence of βtriangles with a common α-triangle edge must end-up with an γ-triangle.
Recall that all edges of an α-triangle are non-spiral edges. Consider a sailing-boat subgraph between S i−1 and S i .
Spiral chain coloring color the vertices as follows: proper color for c(u 2 ) =? But then re-color c ′ (v 3 ) = B and c ′ (u 2 ) = Y (a single Kempe-switch) to resolve impasse on vertex u 2 and maintain 3-coloring of spiral chain (or segment) S i 1 . Of course spiral chain (or segment) S i−1 becomes 4-coloring since B is a safe color of CC 2 and Y is a non-safe color. .. An vertex in the core-spiral receive an unique color form CC 1 based on the adjacent previously colored triangle. In all spiral segments other than the core-spiral assign non-safe color to a vertex whenever is possible. If non-safe color cannot be assigned use respective safe color of the three color classes. In a spiral segment coloring if an vertex is in the sailingboat subgraph and cannot be colored properly then switch safe color with non-safe color between the parallel spiral segments. This operation assures three colorability of the current outer spiral segment at any step. Furthermore three colorability of the outer-spiral segment assures always to find an safe color to assign to the last vertex of the spiral chain.
Therefore we write the following theorem from which the four color theorem follows: Theorem 1. All maximal planar graphs are 4-colorable.
In the next section we will investigate edge-coloring problem of planar graphs under the spiral chain coloring technique.

Spiral Chain Edge Coloring
In 1979 Seymour has conjectured that there is no planar non-elementary critical graph [7]. This conjecture implies the four color theorem, the existence of an algorithm determining the chromatic index of a planar graph in polynomial time and non-existence of planar class two graph with maximum degree at least 6. The latter from 1965 Vizing also proved the case ∆(G) ≥ 8. There are planar class two graphs known with maximum degree 2, 3, 4, and 5. The case ∆(G) = 7 has been settled by using discharging method by Grünwald in his Ph.D. thesis in 2000 [8]. The cyclic spiral coloring algorithm given in this paper not only settles the case ∆(G) = 6 but also answers Seymour's question in affirmative. Another comment about the cyclic spiral chain coloring algorithm is the complexity of the 3-colorability problem of planar graphs.
Let us assume that G a is an almost maximal planar graph with maximum vertex degree 6 such that all its finite faces are triangles. Clearly G a may be made fully maximal by joining its all outer-vertices to another vertex v o . An configuration around the vertex v x ∈ S i is the subgraph of G induced with all adjacent vertices of v x and the vertex v x itself. Consider three sections of spiral chains S i−1 , S i and S i+1 . That is spiral-section S i is neighbor both S i−1 and S i+1 . We say S i+1 is upper-spiral neighbor of v x ∈ S i and S i−1 is lower-spiral neighbor of v x ∈ S i . An triangle in between S i and S i+1 is called upper triangle α u , β u or γ u depending on its type. An triangle in between S i and S i−1 is called lower triangle α l , β l or γ l depending on its type. Then all triangles of an configuration with respect to vertex v x ∈ S i can be written in anticlockwise direction cyclically as an sequence of triangle types α l β l γ l α u β u γ u where the order of α i , β i , γ i , i = l, u depends on the structure of the configuration but we always start from the first lower-triangle. For example in Fig.6 triangles around vertex v x are γ l α l β l β l β u β u .
Step 2. Color anticlockwise direction the edges incident to the first vertex of S k starting the spiral-edge. The coloring rule used here is to assign the first available color from the set of colors C = {c 1 , c 2 , ..., c m }.
Fig. 1.6. Configuration < γ l α l β l β l βu βu > at vertex vx (red lines already colored, blue lines current and black lines future edges to be colored).
In Fig.7 we illustrate CSP algorithm for an maximal planar graph with 12 vertices. The graph has one spiral-chain S and its vertices are v 12 , v 11 , ..., v 1 .
Theorem 2. The algorithm SCE colors the edges of G a with no more than ∆ colors.
Proof : Let C = {c 1 , c 2 , ...} be the set of colors. The proof is based on the argument that cyclic spiral edge coloring of an configuration at a vertex v never creates an impasse or need of use more than ∆ colors. Let us list the possible configurations at a vertex v , where we choose the degree of v as six to show that algorithm works even in the worst case. Bold lines in counterclockwise direction represent three parallel spiral chains S i−1 , S i , S i+1 .
(1) β l β l β l β l β l (2) β l β l β l β l β u β u (3) γ l α l α l γ l β u β u (4) β l β l α l γ l β u β u In configuration β l β l β l β l β l if v is the last vertex of the spiral chain, since all edges incident at v have been colored before we terminate the algorithm. Let us consider configuration (5) γ l α l β l β l β u β u which is shown in Fig.6. In Fig.6 edges in "red" are already colored, in "blue" are the current edges and in "black" lines the future edges that to be colored. Let the three parallel spiral chains be Therefore in all cases (coloring of the edges denoted in blue in Fig.6) it is possible to complete coloring the edges incident v i,2 without needing the seventh color c 7 . It can be verified that this is true for all other configurations (1)- (12). That is chromatic index χ ′ (G a ) = 6 when ∆ = 6. This completes the proof of the theorem. Proof : We note that outer-cycle of an maximal planar graph has a length three and G a is a subgraph of G. Since we assume that ∆(G) = 6 we can obtain G a by deleting some of the outer vertices of G. Let S 1 , S 2 , ..., S k be the spiral chains of G. By Theorem 5 we know that spiral chain edge coloring algorithm colors the edges of G a without any impasse, where in the edgecoloring the order spiral chains is S k , S k−1 , .... When we complete the coloring of G a for some spiral chain S p we can continue in the same way for the other edges of spiral chains in G as long as edges are not incident to the last vertex of the spiral chain. Let v 1 v 2 be the last edge of the spiral chain S 1 . In order to complete the proof we have to give termination condition of the algorithm for edge coloring of G with no more than ∆(G) colors. Since G is an maximal planar graph with ∆(G) = 6, in the worst case (from the point of the spiral edge coloring) we may assume that the degree of the first vertex v 1 of S 1 as d(v 1 ) = 6. We also assume that the vertices of the spiral-chains are ordered from an outer-vertex towards inner vertices of G as V = {v 1 , v 2 , ..., v n }. That is spiral-chains can be written as Clearly v 1 v 2 is a spiral-chain edge and v 1 v i , i = 3, 4, ..., 7 are non-spiral edges. Based on the configuration at vertex v 2 we consider the following: Case 1. Configuration β l β l β l α l γ l at the vertex v 2 , with deg(v 2 ) = 6. Clearly since v 2 is an outer-vertex all triangles of configurations at v 2 must be Configuration β l β l β l β l β l at the vertex v 2 ,with deg(v 2 ) = 6.The graph G with β l β l β l β l β l is shown in Fig. 7(b) together with an proper edge-coloring with χ ′ (G) = 6. In this configuration spiral chain edge coloring algorithm faces with the impasse at the last edge v 2 v 1 . That is we cannot assign c(v 2 v 1 ) = 1 since c(v 2 v 7 ) = 1. But we then have (4, 1)−Kempe chain (v 2 , v 7 , v 9 , v 8 ). So we can re-color edges of this Kempe-chain as c(v 2 v 7 ) = 4, c(v 7 v 9 ) = 1, c(v 9 v 8 ) = 4 and open room for the edge v 2 v 1 to be colored as c(v 2 v 1 ) = 1.
Therefore combining the result that χ′(G) = ∆(G) if G is simple, planar and ∆(G) ≥ 7 Zhao 2001) and Theorem 6 above we can write: Theorem 4. Planar graph G with ∆(G) ≥ 6 is a Class 1. Fig. 10 illustrates spiral edge coloring algorithm for an maximal planar graph G with 12 vertices. Increasing vertex numbers indicate the spiral chain. Therefore edge coloring starts from the first edge (v 12 v 11 ) and assign colors C = {c 1 , c 2 , c 3 , c 4 , c 5 , c 6 } as cyclically in the counterclockwise direction and continue in this way for the other spiral chain edges (v 11 v 10 ), (v 10 v 9 ), ...., (v 2 v 1 ). In the figure we have shown colors as red, yellow, green, light-blue, blue and pink where color red has the highest and color pink has the lowest priority in the cyclic assignment of the colors. Since degree of vertex deg(v 2 ) = 4 < ∆(G), configuration at v 2 would not create any impasse that would otherwise require Kempe-chain switching in order to resolve the impasse. Hence spiral edge-coloring confirms that χ ′ (G) = ∆ for ∆(G) = 6.

Total and Entire Coloring
It is easy to reach the conclusion that chromatic number in the vertex coloring of a graph is related with the maximum size of complete graph minor e.g., Hadwiger Conjecture and chromatic index in the edge coloring of a graph is related with the maximum vertex degree. In the total coloring in which vertices and edges of a graph simultaneously colored and in the entire coloring of a planar graph in which vertex, edge and faces simultaneously colored, chromatic numbers are related mainly with the maximum vertex degree. But as the total and entire colorings of K 4 in Fig. 8 shows vertex colors are dominant over edge and face colors in the process of finding exact colorings. Let us use the terminology used in [22]; denote the vertex, edge, and face sets of G by V (G), E(G), and F (G), respectively. An total coloring of G (where G may not be a planar graph) is a function assigning values (colors) to the elements of V (G) ∪ E(G) and an entire coloring of G (here G is necessarily an (plane) planar graph) is a function assigning values to elements V (G) ∪ E(G) ∪ F (G) in such a way that any two distinct adjacent/incident elements receive distinct colors. The total chromatic number χ(G) a graph G is the least number of colors needed in any total coloring of G. Total coloring conjecture (Behzad, Vizing) asserts the total chromatic number of any graph is bounded by χ(G) ≤ ∆(G) + 2. Here we will be dealing with the open case of planar graphs with maximum vertex degree ∆(G) = 6.
Let C = {c 1 , c 2 , ..., c k } = {1, 2, 3, ...., k} be the set of colors. We will assume that in assigning an color to the element of a graph color c i has a priority over color c j if i < j.
Denote by the sets C v , C e and C f distinct colors used in the coloring vertices, edges and faces of a graph G. For example for the colorings of K 4 in Fig. 8(a) shows a total coloring of K 4 with C t v = {1, 2, 3, 4} , C t e = {1, 2, 3, 4, 5} and Fig. 8(b) shows an entire coloring of K 4 with C e v = {1, 5, 6, 7} , C e e = {1, 2, 3} , C e f = {4, 5, 6, 7} where upper subscript denote type of the coloring and lower subscript denotes type of the element in the graph G.
Note that we have C e v ∩ C e e = φ, C e f ∩ C e e = φ hence we may say that for entire coloring of K 4 edge colors have no influence on the vertex and face colors.

Spiral Chain Total Coloring
Kempe chain in an vertex (edge) coloring of a graph is in most general form is connected two colored subgraph. When the vertices and edges are colored as in total coloring we can talk about mixed Kempe chain.
Definition In an total coloring of G for two vertices v and u (u = v) if the edges of an path P (v, u) ,between v and u colored by two colors c i and c j and c(u) = c j we say the P (v, u) is a (mixed) m -Kempe chain if we have forall w : (uw) ∈ E and c(w) = c i . Algorithm 3.Spiral Total Coloring. Let C = c v1 , c v2 , c v3 , c v4 , c e5 , c e6 , ...., c e(∆+2) be the set of colors. Initially we intentionally reserve the first four colors for the vertices and the other (∆ − 2) colors for the edges of G.
Step 1. Color the vertices ofĠ by using spiral chain vertex coloring algorithm with the colors c v1 , c v2 , c v3 , c v4 .
Step 2. In this step we color the edges of G using spiral chain edge coloring algorithm using the colors in the set C. While assigning an color to an edge give always priority to low index color.
Step 3. If all edges of G colored with no more than ∆ + 2 colors terminate edge-coloring algorithm. If the last edge of the spiral chain creates color conflict then use m-Kempe switch to resolve the color conflict. This will be explained in detail below.
Let (v 1 , v 2 , ..., v n ) be the set of the vertices of a spiral chain S 1 of G with ∆(G) = 6. If G has more than one spiral chains our argument valid for each spiral chains. It is easy to see that at Step 2 of the algorithm as long as we color the edges incident to vertex v i , i > 2 i.e, internal vertex of the spiral chain, since we have colored four edges form the subset of colors reserved for the edges C e = c e5 , c e6 , ...., c e(∆+2) of C and for the other two edges incident v i from the subset of colors C v = {c v1 , c v2 , c v3 , c v4 } which has been used originally for the vertices of G. But when we arrive to color the last spiral-chain edge (v 2 v 1 ) if deg(v 2 ) = ∆(G) we may have a situation that c(v 2 v 1 ) = c(v 2 v y ) where edges incident v y has been handled before by the algorithm. That is proper coloring of the edges incident to the last vertex v 1 of the spiral chain leads to color-conflict. In this case there must another . Hence the four vertices v y , v 2 , v 1 , v x form a m-Kempe chain. By performing m-Kempe-chain switching we can recolor the edges and the vertex v x as: resolve the edge color conflict and complete total coloring of G with ∆ + 2 colors.
From the spiral chain edge and total coloring algorithms we have contributed to the famous total coloring conjecture of Vizing and Behzad: For an illustration consider the total coloring of the graph in Fig.10. Algorithm completes its vertex and edge coloring by assigning "green" to the first edge (v 2 v 1 ) of the spiral chain. But we have c(v 2 v 7 ) = c(v 2 v 1 ). However we have a m -Kempe chain v 2 , v 1 , v 3 . So we apply m-Kempe chain switch as follows: So edge color conflict resolved i.e., c(v 2 v 7 ) = c * (v 2 v 1 ).

Spiral Chain Entire Coloring
Kronk and Mitchem have conjectured that any plane graph of maximum degree ∆ can be colored entirely (simultaneous coloring of vertices, edges and faces) with ∆(G) + 4 colors and showed that this true for ∆(G) = 3 [16].
Other results on this conjecture are first by Borodin for ∆(G) ≥ 12 and then ∆(G) ≥ 7 and finally improved to ∆(G) ≥ 6 by using discharging and nonexistence of an minimal counter example by Sanders and Zhao [21]. The cases ∆(G) ∈ {4, 5} remain undecided. Our solution to entire coloring of plane graph is based on the algorithms given for total and vertex spiral chain coloring of planar graphs and valid for ∆(G) ≥ 3.
Step 1. Find total coloring of G by using spiral chain total coloring algorithm.
Step 2. Find four coloring of the dual of G ′ by using vertex spiral chain coloring algorithm. Use only the last four colors of the set C = c 1 , c 2 , ..., c (∆+4) .
The main theorem can be stated as: Theorem 6. Every plane graph with maximum degree ∆ ≥ 3 is entirely (∆ + 4)-colorable. Fig. 11 illustrates the spiral-chain entire coloring algorithm.  High piority Low piority g2 Fig. 1.11. Entire coloring of a planar graph.

Three color problem with triangles
Grünbaum has shown that planar graphs with at most three triangles are 3-colorable [26]. His conjecture that any planar graph having triangles apart from each other at least distance d ≥ 1 are 3-colorable leads to series of counterexample. Here distance d between the two triangles is the length of the shortest path in the planar graph. Meinikov and Aksionov's counterexample shown in Figure 13 shows that for d ≥ 3 the graph G is not 3-colorable [25], [38]. The reason for this impasse is the (R, Y )-Kempe chain (shown in red dashed line) would not let us to change the only vertex colored in R to a Y color, adjacent to the blue B colored vertex in the graph. But it is possible to reach the same conclusion that graph shown in Figure 13 can only be four colorable since it contains a unique K 4 as a minor; hence by the settled part of Hadwiger's conjecture it is chromatic 4-critical. We have shown a four coloring of G by using spiral chain coloring algorithm in which the last vertex colored by the fourth color blue B. In 1976 Steinberg conjectured that any planar graph without 4-and 5cycles is 3 colorable. In [21] we have given algorithmic proof to this conjecture based again on spiral chains. Here for the sake of completeness we repeat the algorithm which is exactly same in principle with the algorithms given in this paper but the size of the color set is restricted to 3 i.e., C = {1, 2, 3} or {G, Y, R}. Let us denote by G 6 , the class of planar graphs without cycles of size from 4 to 6 and assume that for any vertex v ∈ V (G 6 ) we have deg(v) ≥ 3. That is forbidden subgraphs in G 6 are C 4 , C 5 and any two triangles (cycle of length three) with an common edge. Assume that we have found all spiral chains S 1 , S 2 , ..., S k . Suppose that we have completed spiral chain coloring of G 6 with only using three colors (see [21]) and arrive at the last vertex v 1 of Let us call a "gadget" to a subgraph consist of two triangles with an common vertex. If k is even when vertices of C o must be colored alternatingly with G and Y starting c(v 1 ) = Y and if k is odd all vertices of C o again colored by G and Y except the c(v k ) = R. Let us consider a vertex u ∈ C o with c(u) = G. If we would join u and v 1 without violating the cycle-property of G 6 and obtain a new graph G ′ 6 then since now we have new spiral chain S ′ 1 , the new outercycle C ′ o would be colored at most three colors. From this we conclude that a possible counter-example to the spiral chain coloring algorithm is the one with maximum degree at the first vertex v 1 of S 1 . That is to say that is there graph G with an outer-cycle C o so that spiral chain coloring color vertices of C o with three colors G, Y, R such that the last vertex v 1 in the spiral chain forcibly colored by B (see for example Fig. 2 of almost three colorable graph)? On the other hand in G 6 the outer-cycle vertices must be in the form of serially connected gadgets or vertex of a cycle C i such that |C i | ≥ 6. It can be shown that in this case C o can be colored with two colors and leaving room for the vertex v 1 to be colored with the third color.
In [28] we investigate the 3-colorability problem of a planar graph in more stronger way than the above theorem under the spiral chain coloring. In fact if G has a certain type of (γ, β)-sequences then it is always possible to color it with 3 colors by the spiral chains.
Planar graph shown in Fig.12 is taken from [27] and re-colored by the spiral chain coloring algorithm. Fig. 1.14. Termination of spiral chain edge coloring algorithm with respect to the configuration at vertex v2.

Grötzsch's Theorem Re-visited
Although planar graphs without triangles have been shown to be 3-colorable by H. Gröetzsch [23] in 1958, on going research is still underway on this problem from the point of algorithmic complexity [35], simplification of the proof [35], [39], [40] and various counterparts on the different surfaces [36], [37]. Best bound so far is O(nlogn) has been given by Kowalik [11]. In this section we will give much simpler proof to this theorem with bound O(n) by the use of spiral chain coloring algorithm [19]- [21], [28]. It is an easy fact that chromatic number χ of a cycle C is 2 if |C| ≡ 0(mod2) and is 3 if |C| ≡ 1(mod2). Let v x be a vertex of a cycle C and color the vertices as follow: (1) Start from vertex v x and color the vertices of C in clockwise direction with the sequence of colors 1, 3, 1, 3, .... (2) Start from vertex v x and color the vertices of C in counter clockwise direction with the sequence of colors 1, 2, 1, 2, .... If we start coloring (1) and (2) at the same time we end up with a vertex v y ∈ C for which c(v x ′ ) = 2 or 3 if |C| ≡ 0(mod2). If |C| ≡ 3(mod4) the two sequences end up at two adjacent vertices v y ′ and v y ′′ such that c(v y ′ ) = 2 and c(v y ′′ ) = 3. But color conflict arises when |C| ≡ 1(mod4) such that c(v y ′ ) = c(v y ′′ ) = 1. This simple observation has some importance when we dealing with the algorithmic approaches e.g., spiral chain coloring to the planar graphs without triangles. Spiral chains in G(⋫) We may assume that minimum vertex degree is δ ≥ 3 since degree-two vertex has no effect on the three-colorability of triangle-free planar graph G(⋫). Our proof of Gröetzsch's three color theorem is based on the following two lemmas: trees. Denote these trees by the set F = T p , T p−1 , ..., T 1 which is a spanning forest of G(⋫). That is we have V (T p ) V (T p−1 ) ... V (T 1 ) = V (G(⋫) and V (T p ) V (T p−1 ) ... V (T 1 ) = ∅. Since a tree is also a bipartite graph its chromatic number is two. Therefore we color vertices of each tree T i ∈ F with colors G and Y . Then we re-color arbitrarily one of the vertex to red R of all monochromatic (both green G or both yellow Y ) vertex-pairs (uv) ∈ E(S p ), 1 ≤ p ≤ k, u ∈ T i and v ∈ T j , i = j i.e, c(u) = c(v) = G or Y ⇒ c ′ (u) = G and c ′ (v) = R. This results a 3-coloring of G(⋫).  1.14 illustrates the algorithms given above for three parallel spiral chains S i+1 (upper-spiral-chain), S i (middle-spiral-chain) and S i−1 (lowerspiral-chain). We have also shown 3-coloring of the trees of the non-spiral edges. In Fig. 2.15 we have illustrated spiral chain coloring algorithm for a triangle-free planar graph for which non-spiral edges induce two cycles of length 6 and trees . Bold lines indicate spiral edges while thin dashed lines indicate non-spiral edges. In the graph there are two spiral chains S 1 and S 2 .

Concluding Remarks
In this paper we have given solutions to several planar graph coloring conjectures with the use of spiral chains. The author's 2004 algorithmic spiral-chain coloring proof of the famous four color theorem opens new avenues to the other graph coloring problems [19].
The natural question is this : "Why spiral-chain makes the solution of the problem so easy?" Our answer to this question are several folded. Firstly there is a famous conjecture from the complexity theory that whether P is equal N P or not. It is well known result that if a problem in the class N P has been shown to be in P then all other problems in the N P class would have efficient solutions. Similarly we can say that many problems related with the graphs, particularly planar graphs, would have simple solutions if all of these graphs have Hamiltonian cycles or paths. But we know that some of graphs are not Hamiltonian and in fact finding one in a giving graph is not easy. Hamilton path problem is difficult but the algorithmic answer of finding spiral-chain in graph is almost trivially very easy. Moreover we can easily decided when and how the graph has more than one spiral chains. Therefore spiral chain would act as navigator and paths decomposition in the graph coloring for us to reach the solution. In other words spiral chain is a road-map for efficient coloring algorithm.
Secondly the use of the spiral-chain reduces the number of the cases considerably in the proof. Many other proof methods in the graph coloring theorems are to show nonexistence of minimal counter-examples. But this in most of the times is a very complex task and sometimes we need to investigate case-bycase by only using a computer. Just consider how the possible impasse in the spiral chain proof of the four color theorem is ruled out by re-coloring certain vertex pair in the "sailing boat" subgraph of the maximal planar graph.
I think the third one is the most important. Suppose we start to color the vertices of a planar graph by using spiral chain then you cannot say beforehand whether this process partitioned the graph into, say two parts at the end. Lastly when we color a vertex in the spiral chain we are sure that we will consider another vertex later on that adjacent to the previously colored vertex. That is the main idea that prevents us to fall into the troubles like one of the most elegant "proof" in mathematics [14].
The next question about the use of spiral chains is the following: How one can apply spiral chains to the coloring problems for non-planar graphs? I think a well-defined spiral chains decomposition of a complete graph may help to devise algorithmic solution to the Hadwiger's conjecture [15] which asserts that that every loopless graph not contractible to the complete graph on t + 1 vertices is t-colorable. When t = 3 this is easy, and when t = 4, Wagner's theorem of 1937 shows the conjecture to be equivalent to the fourcolor conjecture (the 4CC) [42]. The case t = 5 it is also equivalent to the 4CC. Without assuming the 4CC Robertson, Seymour and Thomas have shown that every minimal counterexample to Hadwiger's conjecture when t = 5 is apex, that is, it consists of a planar graph with one additional vertex. Consequently, the 4CC implies Hadwiger's conjecture when t = 5, because it implies that apex graphs are 5-colorable [43].