A novel algorithm is proposed for the coloring of planar graphs based on the construction of a maximal independent set S. The maximal independent set S must full l certain characteristics. It must contain the vertex that appears in the maximum number of odd cycles of G. The construction of S considers the internal-face graph of the input graph G in order to select the vertices that decomposes a maximal number of initial faces of G. The traversing in pre-order of the internal-face graph Gf , of the planar graph G, provides us of a strategy in the construction of the maximal independent set S that reduces (G S) in a polygonal tree that will be 3-colorable.
The graph vertex coloring problem consists of coloring the vertices of the graph with the smallest possible number of colors, so that two adjacent vertices can not receive the same color. If such a coloring with k colors exists, the graph is k-colorable. The chromatic number of a graph G, denoted as X(G), represents the minimum number of colors for proper coloring G. The k-colorability problem consists of determining whether an input graph is k-colorable.
The inherent computational complexity, associated with solving NP-hard
problems, has motivated the search for alternative methods, which allow in
polinomial time the solution of special instances of NP-hard problems. For example,
in the case of the vertex coloring problem, 2-coloring is solvable in polinomial
time. Also, in polynomial time has been solved the 3-colorability for some graphs
topologies, such as: AT-free graphs and perfect graphs, as well as to determine
X(G) for some classes of graphs such as: interval graphs, chordal graphs, and
comparability graphs [
Graph vertex coloring is an active eld of research with many interesting subproblems. The graph coloring problem has many applications in areas such as: scheduling problems, frequency allocation, planning, etc. [2{4].
Coloring planar graphs represents a relevant area of interest in graph and
complexity theory, since it involves the frontier between e cient and intratable
computational procedures. Into the set of planar graphs, the polygonal chain
graphs have been a relevant issue of researching in mathematical chemistry,
maybe because they express molecular graphs used to represent the structural
formula of chemical compounds [
The 3-coloring problem has been shown to be a hard problem (NP-complete problem). We propose a novel greedy algorithm for the coloring on planar graphs. Our proposal is based on the logical speci cation of the constraints given by a 3-coloring of an polygonal array as the core of the coloring on planar graphs. 2
Let G = (V; E) be an undirected simple graph (i.e. nite, loop-less and without multiple edges) with vertex set V (or V (G)) and set of edges E(orE(G)). Two vertices v and w are called adjacent if there is an edge v; w 2 E, joining them. The Neighborhood of x 2 V is N (x) = fy 2 V : fx; yg 2 Eg and its closed neighborhood is N (x) [ fxg which is denoted by N [x]. Note that v is not in N (v), but it is in N [v]. We denote the cardinality of a set A, by jAj. The degree of a vertex x 2 V , denoted by (x), is jN (x)j. The maximum degree of G, or just the degree of G, is (G) = maxf (x) : x 2 V g.
A path from a vertex v to w is a sequence of edges: v0v1; v1v2; :::; vn 1vn such that v = v0; vn = w, vk is adjacent to vk+1 and the length of the path is n. A simple path is a path such that v0; v1; :::; vn 1; vn are all di erent. A cycle is just a nonempty path in which the rst and last vertices are identical; and a simple cycle is a cycle in which no vertex is repeated, except the rst and last vertices. A k-cycle is a cycle of length k (it has k edges). A cycle of odd length is called an odd cycle, while a cycle of even length is called an even cycle. A graph without cycles is called acyclic.
Given a subset of vertices S V , the subgraph of G where S is the set of vertices and the set of edges is ffu; vg 2 E : u; v 2 Sg, is called the subgraph of G induced by S, and it is denoted by GjS. G S denotes the graph Gj(V S). The subgraph induced by N (v) is denoted as H(v) = GjN (v), which contains all the nodes of N (v) and all the edges that connect them.
An independent or stable set is a set of vertices in a graph such that none of its vertices is adjacent to another. That is, it is a set S V (G) of vertices such that for any pair of them there is not an edge that connects them.The size of an independent set is the number of vertices it contains. An independent set is maximal if it is not a proper subset of another another independent set, and it is maximum in G if there is not another independent set in G with a cardinality higher than jSj.
A coloring of a graph G = (V; E) is an assignment of colors to its vertices. A coloring is proper if adjacent vertices always have di erent colors. A k-coloring of G is a mapping from V into the set f1,2,...,kg of k "colors". The k- colorability problem consists of deciding wheter an input graph is k-colorable. The chromatic number of G denoted by X(G) is the minimum value k such that G has a proper k-coloring. If X(G) = k, then G is said to be k-chromatic or k- colorable.
Let G = (V; E) be a graph. G is a bipartite graph if V can be partitioned into two subsets U1 and U2, called partite sets, such that every edge of G joins a vertex of U1 to a vertex of U2. If G = (V; E) is a k-chromatic graph, then it is possible to partition V into k independent sets V1; V2; :::; Vk called color classes, but it is not possible to partition V into k 1 independent sets. 3
Planar graphs play play an important role both in the graph theory and in the
graph drawing area. In fact, planar graphs have several interesting properties:
they are sparse, four-colorables, and their inner structure is described succintly
and elegantly [
A drawing of a graph G maps each vertex v to a distinct point (v) of the plane and each edge (u; v) to a simple open Jordan curve (u; v) with endpoints (u) and (v). A drawing is planar if no two distinct edges intersect except, possibly, at common endpoints. A graph is planar if it admits a planar drawing. A planar drawing partitions the plane into connected regions called faces. The unbounded face is usually called external face or outer face. If all the vertices are incident to the outer face the planar drawing is called outerplanar, and the graph admitting it is an outerplanar graph.
Given a planar drawing, the (clockwise) circular order of the edges incident to each vertex is xed. Two planar drawings are equivalent if they determine the same circular orderings of the edges incident to each vertex (sometimes called rotation scheme). A (planar) embedding is an equivalent class of planar drawings and is described by the clockwise circular order of the edges incident to each vertex. A graph put together with one of its planar embedding is sometimes referred to as a plane graph. A non-connected graph is planar if and only if all its connected components are planar.
Perhaps the most renown property is the one stated by Euler's Theorem, which shows that planar graphs are sparse. Namely, given a plane graph with n vertices, m edges and f faces, we have n m + f = 2. A simple corollary that can be deduced from the Euler's rule, is that for a maximal planar graph with at least three vertices, where each face is a triangle, then (2m = 3f ), and as m = 3n 6, and, therefore, for any planar graph we have m 3n 6. This number reduces to m = 2n 3 for maximal outerplanar graphs with at least three vertices (and m 2n 3 for general outerplanar graphs). Also, if n 3 and the graph has no cycle of length 3, then m 2n 4. Finally, if the graph is a tree, then m = n 1.
These considerations allow us to replace m with n in any asymptotic calculation involving planar graphs, while for general graphs only m 2 O(n2) can be assumed. From a more practical perspective, they allow us to decide the nonplanarity of denser graphs without reading all the edges (which would yield a quadratic algorithm).
The rst complete characterization of planar graphs is due to Kuratowsky [
From now on, we consider only planar graphs as working graphs. The purpose
of this research is to determine when a planar graph is 3 or 4-colorable. The
famous four coloring theorem (4CT) [10{12] guarantees us that all planar graph
is 4-colorable. Furthermore, 4CT provides an O(n2) time algorithm to 4-color
any planar graph [
On the other hand, any planar graph triangle-free is 3-colorable, according to
the relevant theorem by Grotszch [
Thus, the hard part to recognize the 3-colorable or 4-colorable planar graphs is when they contain triangles, because it exists planar graphs for both cases.
For example, any planar graph containing K4 or odd wheels will request four colors to proper coloring those graphs. However, those patterns are no the unique 4-colorable cases. If we compose two (or more) wheels sharing one triangle and adding one edge to join the vertices of the last triangle of each wheel, we can form 3 or 4-colorables planar graphs. We show in the following section our proposal for the coloring of planar graphs 4.1
We consider as input a planar graph G = (V; E) whose draw has been already embedded in the plane. Let T res = f1; 2; 3g be the set of the three possible colors to use. To each vertex x 2 V (G) a set of prohibited colors is associated with it, denoted by T abu(x). The following lemma proposes a method for the 3-coloring of acyclic components whose vertices have at most one prohibited color. Lemma 1 An acyclic component where its vertices have at most one color as a restriction is 3-colorable.
Proof 1 The acyclic component is considered as a tree rooted in vr. A pre-order coloring is made from vr, where Color(vr) = M IN fT res T abu(vr)g. When advancing in pre-order in each new level to be colored, all vertex yi in the new level will have at most two restricted colors from its parent node and the color that could exist in T abu(yi). Thus, it has been always available a color of the three possible in T res. The 3-coloring process ends when all nodes of the tree have been visited in pre-order.
We will call the above procedure for coloring acyclic graphs, as the ISAT (G) process. A planar graph G has a set of closed non-intersected regions R = fr1; : : : ; rkg called faces. Each face ri is represented by the set of edges that bound its inside area. All edge fu; vg in G that is not the border of some face from G, is represented by its vertices label uv, and they are called acyclic edges.
Two faces ri; rj 2 R are adjacents if they have common edges, this is, E(ri) \ E(rj ) 6= ;. Otherwise, they are independent faces. Two acyclic edges are adjacents if they share a common endpoint. An acyclic edge is adjacent to a region ri if they have just one common vertex. A set of faces is independent if each pair of them are independent.
Lemma 2 Let A = ff1; f2; : : : ; fng be a set of n faces where each face has at least one vertex that does not restrict color 3. If the set of faces is independent or all of them have a common vertex, then A is 3- colorable Proof 2 This Lemma is shown by induction on the number of faces in the set. 1. For a single face this is 3-colorable, since every cycle with at least one unrestricted vertex is 3-colorable. 2. Suppose that the hypothesis on sets up to n 1 faces is validated. 3. Let A be a set of n faces where each face has at least one vertex that does not restrict color 3. If there is a face fa 2 A that is independent with all other regions in A, since fa is 3-colorable (as in the case 1), fa can be removed from A. The remaining set in A has n 1 faces, and the inductive hypothesis is held.
Otherwise, the n faces in A share a common vertex. Let x 2 fi; 8fi 2 A be the common vertex. If 3 2= T abu(x) then by assigning the color 3 to x and removing it from the graph, all the faces in A become opened and form an acyclic graph, which is 3-colorable by Lemma 1.
Assuming T abu(x) = 3, but 8fi 2 A, there is yi 2 V (fi) such that T abu(yi) = ;. By assigning color 3 to each one of these yi0s, and eliminating them from each V (fi), an acyclic component is formed, that it is 3-colorable by Lemma 1.
Lemma 3 For any vertex v 2 V (G), N [v] is (v) + 1-colorable. Proof 3 Assume that all y 2 N (v) have di erent colors from each other. Then, v has (v) neighborhood colors and it can take only a di erent color from its neighborhood, so N [v] takes (v) + 1 colors. If there are repeated colors in the neighborhood of v, then it is needed the use of at most (v) colors, therefore, N [v] is (v) + 1-colorable.
The previous lemma is applied in the sense that for any vertex of minimal degree (e.g less than 3), 3 colors is enough to be colored. Afterwards, it can be removed at the beginning of any 4-coloring algorithm in order to simplify the resulting graph. Also this Lemma justi es to keep only one edge between adjacent faces, because more than two edges between adjacent faces imply vertices of degree 2 that can be contracted to any of the extremal points of the common boundary between both faces.
We build an internal-face graph Gf = (X; E(Gf )) from G, in the following way: 1. Each face ri 2 R has attached a node x 2 V (Gf ) labeled by its composing edges. 2. Each acyclic edge from G has attached a node of Gf labeled by its vertices label. 3. There is an edge fu; vg 2 E(Gf ) joining two adjacent nodes of Gf when its corresponding faces (or acyclic edges) are adjacent in G. 4. Each edge in Gf is labeled by the common elements (a vertex or edge) between the two adjacent nodes.
Gf is called the internal-face graph of G. Notice that Gf is not the dual graph of G, since in the construction of Gf the external face is not considered. Notice that Gf is a planar graph too, where its nodes represent faces or edges from G, but it is not neccesarily a tree graph. However, if Gf has a tree topology, then we achieve a relevant property for the coloring of G.
When Gf is a tree we call to G, its corresponding planar graph, a polygonal
tree [
Proof 4 Let Gf be the internal-face graph of a planar graph G. Each face of G represented by a node x 2 V (Gf ) is 3-colorable since it is a simple cycle. Furthermore, all acyclic edge of G, represented by a node of Gf , is also 3-colorable since all acyclic graph is in fact 2-colorable. Now, we propose a 3-coloring for G based in traversing the nodes of Gf in pre-order, coloring rst the face of the father node of Gf and after, the faces of its children. In each current level, the two adjacent faces (father and children in G) are considered. Both regions have two common extremal vertices x, y in its common boundaries. Those common vertices are colored rst, and then, the remaining vertices in both faces have two prohibited colors at most. Notice that there is not a pair of adjacent vertices u and v in any of the both faces, such that fu; vg (N (x) \ N (y)), because then fx; y; u; vg form K4 and this subgraph can be not part of any polygonal tree. Thus, for all remaining vertices in both faces, it is available at least one color of the three possible in T res. The 3-coloring process ends when all the nodes of the tree Gf have been visited in pre-order.
The order in the traversing of the common edges between adjacent faces by the previous theorem, provides us maximal paths formed by the common edges and common vertices from the root node until a leaf node of Gf is achieved. This strategy is described in the following procedure. 1. To build the internal-face graph Gf from G. 2. If(Gf is a tree, or it is formed by independent faces, or all faces have a common vertex) then Return(G is 3-Colorable) /* by previous Lemmas and theorem */ 3. Otherwise, let M be the set of common edges between each pair of adjacent faces. 4. To build the maximal independent sets from M . 5. It iterates over each one of the maximal independent sets from M . Let e.g.
S = fs1; s2; : : : ; skg be one of those maximal independent sets. 6. The color 3 is assigned to each si 2 S, and 8y 2 N (si); T abu(y) = 3. 7. G = G S 8. The iteration on the maximal independent sets continues until all the sets are processed. 9. Only the new individual closed regions that were created by coloring the graph will remain in G.
At the end of this process we have as output: If Gf holds the conditions of the lemma or previous theorem, then G is 3-colorable. If the process returns a new graph G0, where there is a face of odd length and all their adjacent vertices are restricted with the color 3, then G is 4-colorable. 4.2
We present now, a polynomial-time algorithm for the coloring of a planar graph G. Given an embedding of a planar graph G, the rst step consists in reducing more than two edges between adjacent faces to only one common edge. It must be removed all v 2 V (G) such that (v) < 3, since those vertices are 3-colorable (based on Lemma 3). Afterwards, a new planar graph Ga is formed from the remaining vertices and edges from G.
Furthermore, if Ga is 3-colorable then G is also 3-colorable. For example, if Ga is a polygonal tree, outerplanar, serial - parallel, or Ga is a triangle-free graph, then G is 3-colorable, based on the previous Lemmas and theorem.
The second step is to choose an initial region of Ga to start the process of vertices-coloring. For this, we look for the region (face) f r where the sum of the degrees of its vertices is maximal. When such region is identi ed, we search for the vertex xa 2 V (f r) of maximum degree to be colored rst, that is: f (xa) = color(xa); 8y 2 N (xa) : T abu(y) = T abu(y) [ ff (xa)g;
Once the rst vertex xa and a color c have been chosen, S = S [ fxag; Ga = Ga fxag, an iterative process is performed with the purpose to form a maximal independet set S from Ga. Thus, the main strategy in our proposal consists in calculating the maximal independent set S of G and assigning a color for every vertex y 2 S. To the remaining graph (G S) is colored by using the ISAT procedure.
The following pseudo-codes apply the above described procedures. Example of planar graph G where the faces are labeled (Figure 1). 5 10 4
2 8
4
A relevant strategy in our algorithm is to consider the vertex appearing in the maximum number of odd cycles of G as part of the maximal independent S to be built. For example, according to the graphs in Figure 1 and 2, two maximal independent sets are: S1 = f2; 4; 6; 8g, and S2 = f1; 4; 7; 11g. However, S2 contains the vertex 11 which appears in the maximum number of odd cycles of G, then S2 is a better option than S1. 9,8 5 1 8 7 6 3 9 3 9 4,9 11,9 11,6
The following tables show the results from step 1 through 7 of the algorithm. For example, Table 1 shows the list of all vertices of G in the rst column, the second column represents the number of odd cycles in which this vertex belongs. Meanwhile, Table 2 shows the vertices obtained after executing the steps 2-8 of the algorithm. After removing the vertices already colored, a base coloring case graph is obtained (applying ISAT), making it a 3-colorable instance. The most expensive time-procedure in our proposal is the algorithm 2. The time-complexity analysis of this procedure follows in this section.
It's known that to build the internal-face graph Gf requires time O(m + n). Into the algorithm 2, the step 1 can be performed in time O(m + n), based in a depth- rst search on G, in order to recognize the parity of the cycles in G. The step 2 requires time O(f ), that in a worst case, it is of order O(m), when the faces in G has minimal lengths. The for in steps: 3 ! 5, consists in visiting all vertex in Gf , that in a worst case, it is also of O(m). The for in steps: 6 ! 8, is similar to previous for, and it has also a time complexity of O(m), in a worst case. The last for (steps: 9 ! 11), consists in visiting all vertex in G, and it has a complexity time of O(n). The most expensive step in algorithm 2 is the last step (step 12). It must to check the constraint for independence vertices in the arrays containing partial maximal independent sets, and in a worst case, it requires time of O(n2). Then, algorithm 2 has a polynomial time complexity of order O(n2). 5
A polynomial-time algorithm for coloring planar ghaphs has beeen shown. Our proposal is based on the computation of a maximal independent set S of the input graph G. The maximal independent set S has some characteristics. One of those is that it contains the vertex that appears in the maximum number of odd cycles of G. The construction of S considers the internal-face graph of G in order to select the vertices that decomposes a maximal number of initial faces of G.
A set of partial maximum sets on the internal-face of the graph are computed. The maximal union of those partial sets form the maximal independent set S, avoiding to visit all vertices of the original graph, and coloring rst the vertices that are crucial for decomposing the input graph in a set of acyclic graphs.