GRAPH-CHROMATIC IMPLICIT RELATIONS JOSEANTONIOMARTINH. 9 0 0 Abstract. Atheoryabouttheimplicationstructureingraphcoloringispre- 2 sented. Discovering hidden relations is a crucial activity in every scientific discipline. The development of mathematical models to study and discover n such hidden relations is of the most highest interest. The main contribution a presentedinthisworkisamodelofhiddenrelationsmaterializedasimplicit- J edgesandimplicit-identitiesinthegraphcoloringproblem,theserelationscan 9 beinterpretedinphysicalandchemicalmodelsashiddenforces,hiddeninter- actions,hiddenreactionsorhiddenvariables. Alsothistheorycanbeextended ] tothecompleteclassofNP-completeproblems. O C . h t Contents a m 1. Introduction 1 [ 2. Preliminary Definitions 2 3. Implicit Relations 3 1 3.1. Implicit Edges 3 v 5 3.2. Implicit Identities 6 5 3.3. Chromatic Polynomials 8 2 3.4. Implicit Relations in planar graphs 9 1 3.5. Implicit Relations and Kempe chains 10 . 1 3.6. Implicit Relations in Critical Graphs 11 0 4. Complexity 12 9 4.1. Polynomial 3-coloring 12 0 4.2. NP and CoNP 13 : v 5. Conclusions 13 i X References 14 r a 1. Introduction All the graphs in this work are simple, that is, unweighted, undirected and containing no graph loops or multiple edges. Graph Vertex Coloring is the task to assign a color to every vertex of a graph in such a way that no two adjacent vertices are assigned the same color, and the chromatic number of a graph, is the minimum number of distinct colors needed to properly color a graph. The importance of graph coloring resides in its general applicability as a process of partitioning a collection of objects into disjoint sets Date:Oct. 2,2006and,inrevisedform,-,-. 1991 Mathematics Subject Classification. Primary05C15,05C75; Secondary05C90,05C69. Key words and phrases. Graph Coloring, Graphs minors, Hadwiger’s conjecture, implicit re- lations,criticalgraphs. 1 2 JOSEANTONIOMARTINH. fulfilling a set of constraints between that objects. For a good reference on graph coloringproblemsthe readercanreviewthe excellentbook ofJensenandToft[17]. Wearepresentingatheoryabouttheimplicationstructureingraphcoloringguided by the concept of implicit edge. We think that the study of this kind of relations has a high applicability in a wide range of experimental and theoretical fields of research. This study can help to unveil a wide range of “hidden” phenomena in a wide range of scientific disciplines like physics, chemistry, and of course, discrete mathematics and computer science. In this work, a formal definition of the Theory of graph-chromatic implicit- relations is presented. The notion of implicit-relation is taken in this work as any relationbetweenasetofverticesofagraphsuchthatdespitethoserelationsarenot containedexplicitly in anyset ofconstraintsor relationsset, for instance the set of edgesofagraph,suchrelationsstillexistforthe graphvertexcoloringproblem. In this way we will define here the implicit-edge relation which means that there is a kind of invisible (but real) edge between two vertices and implicit-identities which means that two different vertices could be treated as the same vertex. In order to formalize such concepts a series of new lemmas and theorems are presented which relate directly these novel concepts with some key aspects of the current theory of graph coloring such as critical graphs, graphs minors, Kempe chains and also with interesting open problems such as the Hadwiger conjecture and the double-critical graphs problem. 2. Preliminary Definitions Partitioning the set of vertices V(G) of a graph G into separate classes, in such a way that no two adjacent vertices are grouped into the same class, is called the vertex graph coloring problem, In order to distinguish such classes, a set of colors C is used, and the division into these classes is given by a ‘proper’ coloring ϕ:V(G)→C, where ϕ(u)6=ϕ(v) for all (u,v) belonging to the set of edges E(G) ofG. AnindependentsetS ofagraphGisasubsetofverticesofGsuchthatthere is no edge between any pair of vertices of S in E(G). Hence we can also define the graph coloring problem as the task of separating the vertices of a graph into a collection of different independent sets. Givenagraphvertexcoloringproblemoveragraph(G)withasetofcolors(C), if (C) has cardinality (k) , then ϕ is a k-coloring of (G). The Chromatic number of a graph χ(G) is the minimum number of colors necessary to color the vertices of a graph G in such a way that no two adjacent vertices are colored with the same color, thus, if χ(G) ≤ k then one says that G is k-colorable and if χ(G) = k then one says that G is k-chromatic. The neighborhood N(v) of v ∈ V(G) is the complete set of vertices that are connected to v. An interesting problem in graph coloringisthecountingtask#k-coloring,thisproblemconsistsincountingthetotal number P(G,k) of distinct k-colorings of a given graph G, it is believed that in computational complexity terms this counting problem is harder than the decision problem of just determining k-colorability in the general case. One standard way of solving the #k-coloring is by using the so called chromatic polynomial which is a polynomial that encodes the number P(G,k). AminorofagraphGisanygraphobtainedbysuccessivecontractionordeletion of edges. GRAPH-CHROMATIC IMPLICIT RELATIONS 3 ∗ Let S (G) = {S1,...,Sn} be the superset of all independent sets of a graph G. ∗ Let us consider the next four operations that could affect S (G): (1) to draw a new edge {x,y} in G: (G+xy). (2) to delete a vertex x of G: (G−x). (3) to identity a pair of vertices {x,y} of G: (G/xy). (4) to contract an edge e={x,y} of G: (G/e). The details of each operation is shown next: (1) Itiseasytoseethattheoperationofdrawinganewedgecouldnotproduce any new independent set, indeed it eliminates at least one independent set ∗ from S . (2) It is alsoeasyto see thatthe operationofdeleting a vertexxfromG could notproduceanynewindependentset,indeediteliminatesatleastasmany ∗ sets from S as the number of sets in which x appears. (3) and 4. Now we show that the two operations (identify and contract) does not produce any new independent set by decomposing them in the two operations firstly studied. Both,vertexidentificationandedgecontractioncouldberealizedbythenextsimple procedure: • Draw a new edge from any vertex joined to y towards x and then delete vertex y. As we can see, both operations drawing a new edge and delete a vertex could not produce any new independent set. This fact can be formalized as the next lemma: Lemma 2.1. Given a graph G and pair of vertices {x,y} of G. ∗ Let S (G) = {S1,...,Sn} be set superset of all independent sets of G and let H be the graph obtained by contracting and edge of G or by identifying a pair of ∗ vertices {x,y} of G and respectively let S (H)={S1,...,Sn} be the superset of all independent sets of H then: ∗ ∗ (2.1) S (H)⊂S (G) Hence any of the four operations listed does not increment the number of inde- pendent sets of a graph. 3. Implicit Relations The chromatic implicit relations are mainly defined by their two most basics concepts, implicit-edges and implicit-identities. 3.1. Implicit Edges. The notionofimplicit-edge is basedonthe simple ideathat in the problem of graph coloring with a fixed number of colors (k), that is, to find a k-coloring of some k-chromatic graph G, there are some independent sets S of vertices of G such that despite those vertices are not joined by an edge we can not findanyk-coloringofGwhereallthe verticesinS arecoloredwiththe samecolor. In order to define precisely the concept of implicit-edge we also fix the cardinality of the subsets S to |S|= 2, that is, we define an implicit-edge as a 2-subset {i,j} of vertices of G. Also, it is shown that the notion of implicit-edge is invariant to the fact that the 2-subset {i,j} belongs to the set of edges of G or not. If a 2-subset {i,j} is an implicit-edge and {i,j} belongs to the set of edges of G we say that {i,j} is a 4 JOSEANTONIOMARTINH. drawn implicit-edge and if {i,j} does not belongs to the set of edges of G we say that {i,j} is a non-drawn implicit-edge. Now we will define in strict sense the notion of implicit-edge: Definition 3.1. Implicit Edge. Given a graph G and an integer k, we say that the subset {i,j} of vertices of G is an implicit-edge if and only if there is no k-coloringof the graphG−ij such thatverticesiandj receivethesamecolorbeingthegraphG−ij thegraphGwith a possible edge {i,j} deleted, hence {i,j} is an implicit-edge in the graph G−ij too. Alteratively, we can say that the set of all k-colorings of G−ij where i and j receive the same color is the empty set. Also we must note that implicit-edges {i,j} could belong to the set of edges of G or not but the set of all k-colorings is the same in both cases. In order to illustrate this notion we will use a trivial case, that is, a bipartite (2-chromatic)graphG. Implicit-edges in 2-chromaticgraphsare defined veryeasy: every subset {i,j} of vertices of G with an odd length path between them are implicit-edges. Let us take the graph G as the four-path: i◦—◦—◦—◦j We can easily see that {i,j} is an implicit-edge of G indeed the only implicit- edge of G. Also, if we draw the edge {i,j} we get a square and then all edges are now implicit-edges. Morecomplexexamplesareshownnextforthe 3-coloringcase. Inthe graph(a) of Fig. 1., there is an implicit edge between the vertices {u,v}. As one can easily see, coloring the vertices {u,v} with the same color leads to an impossibility for coloring the graph with only three colors. The same fact can be verified in the graph (b) of Fig. 1., there is an implicit edge between the vertices {u,v}. v u v u u v (a) (b) (c) Figure 1. Implicit edges in 3-coloring of 3-chromatic graphs. Also, in the graph (c) of Fig. 1 exist and implicit edge between the vertices {u,v},becauseitsneighborhoodisa5-cycleanda5-cycleisnot2-colorable. Inthis example we show a more generalizable implication structure, showing that if two vertices conforms the neighborhood of a subgraph H with χ(H) = 3 then; these two vertices can not be colored with the same color because its adjacency is not 2-colorable. Theorem 3.2. Implicit Edges and Independent Sets. Given a k-chromatic graph G, the subset {i,j} of vertices of G is an implicit-edge if and only if there is no independent set S of G−ij containing the vertices {i,j} such that the removal of S from G results in a subgraph H of G with a chromatic number less than k. GRAPH-CHROMATIC IMPLICIT RELATIONS 5 Proof. Given a k-chromatic graph G and let i and j be to vertices of G: 1) Assume that {i,j} is an implicit-edge. Let us suppose that by removing an independent set S of G−ij containing the verticesiandj the resultinggraphH =G−S is (k-1)-colorable. Thenwecanfind a (k-1)-coloring of the graph H and restore all the vertices in S and assign them the color k and thus there will be a k-coloring of the graph G−ij where vertices i and j are colored with the same color and this contradicts the assumption that {i,j} is an implicit-edge. 2) Assume that {i,j} is not an implicit-edge. Then by definition there is a k-coloringof G−ij such that the vertices {i,j} are colored with the same color and then there will be an independent set S of G−ij containing the vertices {i,j} (i.e. a color class) such that the removal of S from G will result in a subgraph H of G with a chromatic number less than k. (cid:3) As it is known another way of defining the graph coloring problem is the task of partitioning the graph into different independent sets and thus the chromatic numberisthen definedasthe minimum numberofpartitionsthatcanbe achieved. Here the interesting fact is the relationof this definition and the Theorem3.2 that yields the definition of a critical independent set. Definition 3.3. Critical Independent Set. Given a k-chromatic graph G, we say that an independent set S is critical if and only if χ(G−S)=(k−1), that is, S is a color class of some k-coloring of G. Fromthisdefinitionfollowsthatcriticalindependentsetscannotcontainimplicit- edges. Theorem 3.4. Implicit Edge invariant. If there are implicit-edges in a k-chromatic graph then by removing any criti- cal independent set the resulting graph is (k-1)-chromatic with at least the same implicit-edges. Proof. Givena k-chromaticgraphGandletiandjbe to verticesofG where{i,j} is an implicit-edge: Remove a critical independent set of G, let us suppose that now {i,j} is not an implicit-edge thus find a coloring where {i,j} receive the same color, then restore the critical independent set with all vertices colored the same. The graph G is k-colored and {i,j} has the same color and this contradicts the fact that {i,j} is an implicit-edge of G. (cid:3) Theorem 3.5. Implicit Edge (alternative definition on bipartite subgraphs). Given a k-chromatic graph G. A subset {i,j} of vertices of G is an implicit-edge if and only if {i,j} is an implicit-edge of H for all subgraph H <G such that: H =G−{S1,...,Sk−2} ; for any combination of cardinality (k−2) of Si, being each S any critical independent set of G (a color class of some k-coloring i of G) and H a bipartite graph, that is, vertices {i,j} have distinct color in every 2-coloringofH,thatis, thereis anoddlengthpathbetween{i,j}afteranyarbitrary deletion of (k−2) color classes of G. 6 JOSEANTONIOMARTINH. Proof. Given a k-chromatic graph G if {i,j} is an edge of G delete this edge from G. i) Let the subset {i,j}of vertices of G be animplicit-edge. Then by Theorem3.16 in all k-colorings of G will exists a kempe-chain Ω of length l ≥ 3 with colors ij (c(i),c(j)) where (c(i) 6= c(j)) and vertices {i,j} in its extremes thus by deleting (k−2) color classes in any k-coloring of G you get a bipartite subgraph H of G (the respective kempe-chain)in which vertices {i,j}receive different color,that is, {i,j} is an implicit edge of H. ii) Let the subset {i,j} of vertices of G not be an implicit-edge. Then simply find a k-coloring of G such that vertices {i,j} are colored with the same color, thus you can delete k−2 color classes and obtain a 2-colorable subgraph H of G in which vertices {i,j} are colored with the same color and hence {i,j} is not an implicit-edge of some H. (cid:3) It is necessary to emphasize the importance of Theorem 3.5. This theorem impliesthatwecanexplainImplicitEdgesink-chromaticgraphsintermsofinduced bipartite subgraphs. In simple words: if {i,j} is an implicit-edge of a k-chromatic graph G then by deleting (k-2) arbitrary critical independent sets (color classes of G) we obtain a bipartite graph H <G where {i,j} is an implicit-edge too, and, if {i,j}isnotanimplicit-edgeofG,thenwouldbeacombinationofcardinality(k-2) critical independent sets (color classes of G) such that H = G−{S1,...,Sk−2} is at most bipartite (2-colorable) and {i,j} is not an implicit-edge of H, this is due to kempe-chains definition of implicit-edge. Definition 3.6. Explicit Neighborhood. Givenak-chromaticgraphG,The ExplicitNeighborhoodEN (v) ofonev ∈V is k the complete set of verticesthat arejoined by implicit or explicit edges to a vertex v of G. This concept extends the notion of neighborhood to include the implicit edges. As an example, we can see in Figure 1 (a) that the neighborhood of vertex {2} is: {1,4} but its Explicit Neighborhood for every 3-coloring of G: EN3(v = 2) is {1,4,5}. Definition 3.7. Explicit Graph. ′ ′ Given an integer k and a graph G, an Explicit Graph is a graph G such that G k k does not have implicit edges for a k-coloring problem of G. We can define the operator G′ = Ψk(G) as the operator which represents a procedurethattransformthegraphGintoitsexplicitrepresentation,thatis,Ψk(G) ′ ′ copy the graphG into G and add all the implicit edges of G to G for a k-coloring problem. It is important to note that critical graphs are explicit graphs, that is, critical graphsdoesnothaveimplicit-relations,this factwillbe showninthe sectionabout critical graphs. 3.2. ImplicitIdentities. Implicit-Identitiesareinmostcasestheopposite-equivalent of Implicit-Edges, so there will be an almost one to one collection of theorems and lemmaswhichareequivalent. Whileimplicit-edgesaredefinedasarelationinwhich GRAPH-CHROMATIC IMPLICIT RELATIONS 7 vertices receive always different color implicit-identities are the opposite relation, that is, the vertices receive always the same color. Definition 3.8. Implicit Identity. Given a k-chromatic graphG, we say that the subset {i,j} of vertices of G where {i,j}is not an edge of G is an implicit-identity if and only if in every k-coloringof G the subset {i,j} is colored with the same color. Note that contrary to implicit-edges, if we add and edge e = {i,j} to a graph G the resulting graph G+e will not be k-colorable and e will be a critical edge of G+e. Theorem 3.9. Implicit Identities and Independent Sets. Given a k-chromatic graph G, the subset {i,j} of vertices of G where {i,j} is not an edge of G is an implicit-identity if and only if there is no independent set S in G containing the vertex i or containing vertex j but not both such that, the complete removal of S from G, results in a subgraph H <G with chromatic number less than k. Proof. Given a k-chromatic graph G and let i and j be to vertices of G: 1) Assume that {i,j} is an implicit-identity. Let us suppose that by removing an independent set S of G containing the ver- tex i or j (but not both) the resulting graph H = G−S will be (k-1)-colorable. Then we can find a (k-1)-coloring of H and restore all the vertices of S assigning themthe colork,thus there willbe ak-coloringofGwherethe verticesiandjwill be colored with distinct color and this contradicts the assumption that {i,j} is an implicit-identity. 2) Assume that {i,j} is not an implicit-identity. Thenbydefinitionthereisak-coloringofGsuchthatthe independentset{i,j} is colored with different color. Then there is an independent set S of G containing the vertex i or j (but not both) (i.e. a color class) such that the removalof S from G will result in a subgraph H of G with a chromatic number less than k. (cid:3) Theorem 3.10. Implicit Identity Invariant. If there is an implicit-identity {i,j} in a k-chromatic graph then by removing any critical independent set not containing {i,j} the resulting graph is (k-1)-chromatic with {i,j} being an implicit-identity. Proof. Givena k-chromaticgraphG, let i andj be to verticesof G suchthat {i,j} is an implicit-identity. Remove a critical independent set S of G not containing i nor j and find a (k- 1)-coloring of G where {i,j} receive different color. Then restore the critical in- dependent set S with all vertices colored the same. Thus the graph G is now k-coloredand{i,j} havedifferent colors,but this contradicts the fact that {i,j} is an implicit-identity of G. (cid:3) Theorem 3.11. Implicit Identity (alternative definition on bipartite subgraphs). Given a k-chromatic graph G(V,E), the pair {i,j}∈V(G) is an implicit-identity of G if and only if {i,j}∈V(H) is an implicit-identity of H for all H <G such that: H =G−{S1,...,Sk−2} ; for any combination of cardinality (k−2) of Si , 8 JOSEANTONIOMARTINH. being each S any critical independent set in G (i.e. a color class) not including i vertices{i,j}andHabipartitegraph. Thatis,vertices{i,j}∈V(H)havethesame color in every proper coloring of H, that is, there is an even length path between {i,j} after any arbitrary deletion of (k-2) color classes of G not containing vertices {i,j}∈V(G). Proof. Given a k-chromatic graph G with a pair of vertices {i,j} where {i,j} is not an edge, then: i) Let the subset {i,j} of vertices of G be an implicit-identity. Then by Theo- rem 3.15 in all k-colorings of G will exists at least kempe-chain Ω of length l≥2 ij withcolors(c(i),c(j))where(c(i)=c(j))andvertices{i,j}initsextremesthusby deleting (k−2) colorclasses in any k-coloringof G youget a bipartite subgraphH of G (the respective kempe-chains) in which vertices {i,j} receive the same color, that is, {i,j} is an implicit edge of H. ii) Let the subset {i,j} of vertices of G not to be an implicit-identity. Then sim- ply find a k-coloring of G such that vertices {i,j} are colored with different color, thus you can delete k−2 color classes and obtain a 2-colorable subgraph H of G in which vertices {i,j} are colored with different color and hence {i,j} is not an implicit-identity of some H. (cid:3) It is necessary to emphasize the importance of Theorem 3.11. This Definition implies that we can explain Implicit Identities in k-chromatic graphs in terms of induced bipartite subgraphs. In simple words: if {i,j} is an implicit-identity of a k-chromatic graph G then by deleting (k-2) arbitrary critical independent sets (colorclassesofG)nocontaining{i,j}∈V(G)weobtainabipartitegraphH <G where {i,j} is an implicit-identity too, and, if {i,j} is not an implicit-identity of G,thenwouldbeacombinationofcardinality(k-2)criticalindependentsets(color classes of G) such that: H =G−{S1,...,Sk−2} , is at most bipartite (2-colorable)and {i,j} is not an implicit-identity of H. This isimportantbecauseimplicit-identities inbipartitegraphsaredefinedvery easy: every pair of vertices with an even length path between them are implicit identities, i.e. i•—•—•j then {i,j} is an implicit-identity. 3.3. Chromatic Polynomials. A fundamental field of researchin graphcoloring theory are the Chromatic Polynomials P(G,k), see [12]. The chromatic polynomial P(G,k) for a given graph is a polynomial which en- codes the number of different k-colorings of a graph G, thus, we can denote the number of proper k-colorings of a graph G as P(G,k). The Chromatic Polynomi- als where first used by Birkhoff and Lewis [5, 6] in their attack on the four-color theorem. One of the defining features of the chromatic polynomial P(G,k) also called the Fundamental Reduction Theorem (F.R.T) [12](pp.4–6) of a graph G is that it satisfies the deletion-contraction relation: If{e}isanedgeofGjoiningvertices{x}and{y},letG−ebethegraphGwith {e}deleted andletG/e be the graphresultingfromthe contractionofvertices{x} GRAPH-CHROMATIC IMPLICIT RELATIONS 9 and {y}. Then: (3.1) P(G,k)=P(G−e,k)−P(G/e,k) Also, the next equation is part of the so called F.R.T. Let {x} and {y} be two non-adjacent vertices in a graph G and let G+xy be the graph with a new edge e={x,y}. Then: (3.2) P(G,k)=P(G+e,k)+P(G/e,k) A direct consequence of Eq. 3.1, Eq. 3.2 and the definition of implicit relations is presented as two new theorems (3.12,3.14): Theorem 3.12. Fundamental Reduction Theorem under implicit-edges. If G is a k-chromatic graph and e={x,y} is an implicit edge of G (drawn ornot). Then P(G/e,k)=0, that is, the graph (G/e) is not k-colorable. Proof. of Theorem 3.12 Being {e} an implicit-edge of a k-chromatic graph G: P(G,k) = P(G−e,k) or respectively (drawn or not) P(G,k)=P(G+e,k) thus: P(G,k)=P(G−e,k)=⇒P(G/e,k)=0 due to Eq. 3.1. P(G,k)=P(G+e,k)=⇒P(G/e,k)=0 due to Eq. 3.2. (cid:3) Corollary 3.13. of theorem 3.12 Given a minor-closed class G of graphs (i.e. if G∈G and G≥H, then H ∈G). BeingGak-chromaticgraphinG and{e}adrawnimplicitedgeofG.Ifwecontract the edge {e} the resulting graph is a (k+1)-chromatic graph in G. Also, in general any contraction of an implicit edge (drawn or not) will result in a (k+1)-chromatic graph. And in the same sense for the implicit-identities case: Theorem 3.14. Fundamental Reduction Theorem under implicit-identities. If G is a k-chromatic graph and e={x,y} is an implicit-identity of G. Then P(G,k)=P(G/e,k). Proof. of Theorem 3.14 Being {e} an implicit-identity of a k-chromatic graph G: P(G+e,k)=0 thus: P(G+e,k)=0=⇒P(G,k)=P(G/e,k) due to Eq. 3.2. (cid:3) 3.4. Implicit Relations in planar graphs. An important type of graphs are the planar graphs, a graph is called planar: if it can be drawn in a plane without edges crossings. It is important to show that 3-coloring planar graphs remains NP-Complete [14]. Planar graphs poses the next important properties: a): Every planar graph is four colorable [1, 2, 3, 4, 20, 19]. b): Every planar graph without triangles is 3-colorable[17, 16, 15]. c): Planar graphs are closed under edge contraction, that is, every edge con- traction of a planar graph results in a new planar graph. 10 JOSEANTONIOMARTINH. The most important property for our purposes is the property (a) due to the celebrated four-color-conjecture that now is called after [1, 2, 3] the four color theorem. Given the fact that every planar graph is four colorable there are some interesting questions: - There are implicit edges in 4-coloring of planar graphs? - Are the proofs of [1, 2, 3, 4, 20, 19] affected in some way by the existence of implicit edges?. The first question is affirmative, there are implicit edges in 4-coloring of planar graphs as can be seen in Figure 2. u u v v (a) (b) Figure 2. Implicit edges in 4-chromatic graphs. The main observation from Figure 2 is that the implicit edge can not be drawn without edge line crossings, it is straightforward to proof the fact that if implicit edges in 4-coloring of planar graphs could be drawn without edge line crossings, thenthetheoremsin[1,2,3,4,20,19]arefalseduetothecorollaryofTheorem3.12. 3.5. Implicit Relations and Kempe chains. Kempe chains were first used by AlfredKempeinhisattemptofaproofofthefourcolorstheorem[13]. Althoughhis proof was not valid his method of color chains remained as a useful tool, indeed it isusedinmodernproofslikenewcomputerbasedproofsofthefourcolorstheorem see [3, 20]. Next we provide a simple definition of Kempe Chains. Let G be a graph with vertex set V, and we provide a proper coloring function: ϕ:V(G)→C , where C is a finite set of colors, containing at least two distinct colors c1 and c2. If {v} is a vertex with color c1, then the (c1,c2)-Kempe chain of G is the maximal connected subset of V which contains {v} and whose vertices are all colored either c1 or c2, i.e. a simple bipartite component of G colored with colors c1 and c2. One of the useful characteristics of Kempe chains is the well known process of flipping. This process consist in taking a kempe chain Ω of colors c1 and c2 and change all vertices of Ω with color c1 to c2 and all vertices with color c2 to c1, indeed this was the basic mechanism of the failed proof the four color theorem by Kempe.