Graph Coloring - Amirkabir University of Technology

GRAPH COLORING Hamid Alaei Vertex Coloring (Vertex) Coloring of a graph G = (V,E) is a map function c : V C C: set of colors for every edge vw E: c(v) c(w). chromatic number (G) is the minimal number of colors needed in a coloring of G. k-coloring of a graph: ... k-colorable graph: ... k-chromatic graph: ... equivalent colorings of a graph: ... 2 Vertex Colori ng

Exam ple Bipart ite Graph (G) = 2 3 Vertex Colori ng Exam ple Icosah edron (G) = 4 4 Application

Constraint Scheduling Tasks: { T1, ..., Tn} Concurrency Constraint: unsharable resources Conflict Matrix C: C(i, j) = 0: Ti and Tj need no common resources C(i, j) = 1: otherwise Conflict Graph G: a graph with adjacency matrix C G is k-colorable iff tasks can be schedules in k time intervel 5

Vertex Coloring Upper Bounds Procedure COLOR(G, v; c) 1. c(v1) 1; 2. for i = 2 to n do 3. c(vi) min {j : c(vh) j for all h = 1, . . . , i 1 with h adjacency list Ai } 4. Od Lemma 1: Let G be a graph. Then (G) (G)+1, where (G) denotes the maximal degree of a vertex of G. Example: Complete Graph: (Kn) = n = (Kn) + 1 Cycle of odd length: (C2n+1) = 3 = (C2n+1)+1 6 Vertex Coloring

Upper Bounds Lemma 2: Let G = (V,E) be a graph. Then: (G) 1 + max {(H): H is an induced subgraph of ): H): H is an induced subgraph of is an induced subgraph of G} (H): H is an induced subgraph of ): the minimal degree of a vertex of H. Order(G; v) 1. vn a vertex in G with minimum degree 2. Order(G \ vn; ) Corollary 3: Let G be a connected graph, and assume that G is not regular. Then (G) (G). 7 Vertex Coloring Upper Bounds Corollary 3: Let G be a connected graph, and assume that G is not regular. Then (G) (G). Proof: 1. Let (G) = (G) + 1

2. Let H): H is an induced subgraph of is a induced subgraph of G, maximize (H): H is an induced subgraph of ) 3. (G) 1 + (H): H is an induced subgraph of ) 4. (G) = (H): H is an induced subgraph of ) 5. H): H is an induced subgraph of is (G)-regular 6. H is not connected to any vertex outside H 7. H): H is an induced subgraph of = G 8. G is (G)-regular 8 Vertex Colori ng Upper Bound s Broo ks Theor em Theorem 4: Let G be a connected graph which is neither complete nor a cycle of odd length. Then (G) (G).

Proof: Let G be regular of degree k = (G) k = 2 means G is a cycle Let k 3 First: G is not 2-connected 1. 2. 3. Let v be a cut vertex and V1, . . . , Vl be the connected components of G \ v Induction on # of vertices: Vi {v} is k colorable G is k-colorable 9 Vertex Colori ng Upper Bound s

Broo ks Theor em Let G be 2-connected Assertion: v1, v2, vn H): H is an induced subgraph of = G \ {v1, v2} is connected v1vn and v2vn E v1 v1v2 E v2 vn Order(G; v) 1. find vertices v1, v2, vn satisfying the above constraints 2. for i = n -1, ... , 3 do 3. vi a vertex in V \ {v1, v2, vi+1, . . . , vn} adjacent to at least one of the vertices vi+1, . . . , vn 4. od 10 Vertex Colori

ng Upper Bound s Broo ks Theor em G contains such vertices: v1 suppose G is even 3-connected: v2 vn vn an arbitrary vertex v1 , v2 non-adjacent vertices, adjacent to v n Note that the set (vn) of vertices adjacent to v n has to contain two non-adjacent vertices v1 and v2. Otherwise the k + 1 vertices in (vn) {vvn} form a complete graph Kk+1 because of the connectedness and the kregularity of G, this graph would have to be G itself which contradicts the hypothesis of the theorem. 11

Vertex Colori ng Broo ks Theor em Upper Bound s v1 G contains such vertices: v2 suppose G is 2-connected but not 3connected: {v, vn} a vertex separator Let V1, ..., Vk be connected components of G \ {v, vn} vn has to have some neighbor in each V i, as otherwise G\ v would not be connected we choose two neighbors v1 V1 and v2 V2 of vn G \ {v1, v2} is connected (why?) vn

12 Vertex Coloring Complexity The bound (G) (G) may be arbitrarily bad: bipartite graphs determining (G) is an NP-hard problem If P NP holds, then there is not even a polynomial algorithm producing an approximate solution which always needs less than 2(G) colors There is an algorithm of complexity O(|V | + |E| log k) which, with probability almost 1, colors any

given k-colorable graph with k colors!!! 13 Vertex Colori ng Compl exity Zero Knowl edge Passw ord Security problem: restrict access to a system to a list of valid users For each user randomly generate a 3-colorable graph G (user ID) Log in: user prove ownership of the graph by 3coloring it: 1. 2. 3. 4.

5. User: Lay the graph on the table with its vertices covered Observer: pick a random pair of adjacent vertices User: expose their color User: secretly and randomly permute colors Repeat the procedure until the observer satisfied we can 3-color the graph Prob(deceive observer in n successive trials) (1 r)n 14 Vertex Colori ng Peters en Graph Exam ple

G has an odd length cycle 3 (G) G is neither complete nor odd cycle (G) (G) = 3 (G) = 3 15 Vertex Coloring Planar Graphs Theorem 5(4-color theorem): If G is a planar graph (G) 4 Generalization of 4-color theorem Genus of a connected orientable surface is an integer representing the maximum number of cutting along non intersecting closed simple curve without rendering the resulting manifold disconnected

The chromatic number of a surface S is the maximum chromatic number of all graphs that can be embedded on S Theorem 6 (Heawood Map-Coloring Theorem): For every positive integer N, the chromatic number of a surface of genus N is the greatest integer in (7 + (1 + 48N)(1/2))/2 16 Vertex Colori ng Planar Graph s Five Color Theor em Theorem 7 (5-color theorem): If G is a planar graph (G) 5 Proof: based on induction on |V(G)| and relies on

the existence of a vertex v in G of degree at most 5. We assume that G\v is 5 colorable then we show how to extend it to 5-coloring of G We denote colors by 1 .. 5 If neighbors of v used no more than 4 colors then we color v with one of 5 colors not used by any of its neighbor Otherwise, we first modify coloring so neighbors use only 4 colors 17 Vertex Colori ng Planar Graph s FiveColor Theor em H): H is an induced subgraph of (i, j): induced subgraph of G\v by vertices colored i and j. Assume neighbors of v: v1, ..., v5 arranged in clockwise

order in some planar representation of G and vi has color i Two cases: 1. v1 and v3 are in different components of H(1, 3), named H1(1, 3) and H3(1, 3) invert colors on vertices in H): H is an induced subgraph of 1(1, 3) 2. v1 and v3 are in the same component of H(1, 3) There is a path p from v1 to v3. p together with (v, v1) and (v, v3) determine a cycle C in G. One of v2 and v4 is lied in the interior of C and other in its exterior v2 and v4 cannot lie in the same component of H): H is an induced subgraph of (2, 4) Back to case 1. 18 Vertex Colori ng Planar Graph s FiveColor Algori thm 1

Procedure Five-Color1(G) 1. if(|V(G)| 5) 2. then find a trivial coloring of G 3. else select v in V(G) of degree at most 5 4. Five-color1(G \ v) 5. if adj(v) use 5 colors 6. then find i and j in adj(v) from distinct components C1 and C2 of the subgraph induced by the vertices colored the same as i and j 7. for each w in C1 do if color(w) = color(i) 8. then set color(w) to color(j) 9. else set color(w) to color(i) 10. set color(v) to color not used in adj(v) 11. End 19 Vertex

Colori ng Planar FiveColor Algori thm 2 Procedure Five-Color2(G) 1. if(|V(G)| 5) 2. then find a trivial coloring of G, return 3. else if there is a vertex v of degree 4 or less 4. then delete v from G 5. else let v be a vertex of degree 5 6. let x and y be two nonadjacent neighbors of v 7. delete v from G, and identify x and y 8. let G' be the resulting planar graph 9. Five-Color2(G') 10. assign to each identified vertex the color of the substituting vertex; set color(v) to color not used in adj(v) 11. End

20 Vertex Colori ng Planar FiveColor Algori thm 2 Identification of x and y: O(d(x) + d(y)) Same vertex may appear in identification O(n) times So a direct implementation of algorithm would request O(n2) time There is an online algorithm execute any sequence of identification of a general graph in O(m log n) time by using adjacency lists together with an adjacency matrix It yield a simple O(n log n) 5-coloring algorithm 21

Vertex Colori ng Planar Batch Proces sing Algori thm It runs in several stages Each stage processes a batch of vertices provided any vertex is not involved in more than 2 identifications so the stage requires O(n) time It processes vertices of degree at most 6 Each stage eliminate at least 3/17 of vertices Given the planar embedding of G, run time of algorithm is O(n) 22 Vertex Colori ng

Planar Graph s Batch Proces sing Algori thm Construction of the reduced graph G' If G contains a vertex v of degree at most 4 then Delete Else if G contains a vertex v of degree 5 such that at most one of the neighbors has been involved in identifications so far during the current stage Delete v v; Identify 2 nonadjacent neighbor of v

Else if G contains a vertex v of degree 6 such that no neighbors of v has been involved in identifications so far during the current stage Delete v; Identify 3 nonadjacent neighbors of v or 2 parallel pairs of neighbors of v 23 Vertex Colori ng Planar Graph s Batch Proces sing Algori thm Lemma 8: Let a planar graph G = ( V , E ) contain a vertex v of degree 5 with N(v) = {v 1, v2, v3, v4, v5}. Then, for any specified vi N(v), v has a pair of nonadjacent neighbors vj and vk other than vi.

Furthermore one can find such a pair in O(minvN(v)d(v(v )) time if the planar embedding of G is given. Proof: 1. Assume vi = v1 and v1 .. V5 are labelled clockwise in the planar embeding of G 2. Consider the case d(v2) is minimum among all d(vi) 3. Scanning the adjacency list of v2 in O(d(v2)) time, one know whether (v2, v4) E 4. If (v2, v4) E then (v3, v5) E 24 Vertex Colori ng Planar Graph s Batch Proces sing Algori thm

Lemma 9: Let a planar graph G = (V, E) contain a vertex of degree 6 with N(v) = {v1, v2, v3, v4, v5, v6}. Then v has either i. Three pairwise nonadjacent neighbors or ii. Two parallel pairs and of nonadjacent neighbors Furthermore one can find these neighbors in O(min 1s t 6 [d(vs)+d(vt)]) time if the planar embedding of G is given. Proof: Let v1, v2, ..., v6 be the neighbors of v listed in cyclic order Assume d(v1) and d(v2) is minimum among all the sums of degrees of two neighbors. Proof for remaining cases is similar 25 Vertex Colori ng

1. 2. 3. 4. 5. Planar Graph s Batch Proces sing Algori thm Scanning the adjacency list of v1 and v2 one can find whether the edges (v1, v5) and (v2, v4) exist or not If exactly one of them exists, say (v1, v5) then v2, v4, v6 are the required three neighbors Otherwise, if both exist {vv6, v2} and {vv3, v5} And if neither exist {vv1, v5} and {vv2, v4} are required two parallel nonadjacent neighbors Time required is O(d(v1)+ d(v2))

26 Vertex Colori ng Planar Graph s Batch Proces sing Algori thm

Data structure An doubly linked adjacency list Adj(v) for each v V Two copy of each edge (u, v): in Adj(u) and Adj(v) Arrays: Flag, Count, Deg and Point Queues: Q(4), Q(5), Q(6) Flag(v) = true iff v is identified in the current stage Count(v) = number of neighbors w with FLAG(w) = true Deg(v) = value of d(v) Q(4) = {v v | Deg(v) 4} Q(5) = {vv | Deg(v) =5, Count(v)=1} Q(6) = {vv | Deg(v) =6, Count(v)=0} Point(v) = pointer to an element v in Q(i) 27 Vertex Colori ng 1. 2. 3. 4. 5. 6. 7.

8. Planar Graph s Batch Proces sing Algori thm Procedure Five Embed a given planar graph G in the plane For each v V do Calculate Deg(v) Flag(v) false Count(v) 0 Initialize Q(4), Q(5) and Q(6) Color(G) End. 28 Vertex Colori ng 1.

2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. Planar Graph s Batch Proces sing Algori thm Procedure Color(G) if |V| 5 then find a trivial 5-coloring of G; return if all Q(i) are empty {vcurrent stage is over} reset Flag, Count, and Q {vStart a new stage}

if Q(4) is not empty take a top entry v from Q(4) Delete(v) let G' be the reduced graph else if Q(5) is not empty take a top entry v from Q(5) choose two nonadjacent neighbors x, y such that Flag(x) = Flag(y) = false Delete(v) Identify(x, y) let G' be the reduced graph 29 Vertex Colori ng 14. 15. 16. 17. 18. 19. 20. 21. 22.

23. Planar Graph s Batch Proces sing Algori thm Procedure Color(G) else (* if Q(6) in not empty *) take a top entry v from Q(6) {vby lemma 10 either case(i) or case(ii) holds for case (i) let x, y, z be 3 pairwise nonadjacent neighbors of v Delete(v); Identify(y, x); Identify(z, x) for case (ii) let {vw, x} and {vy, z} be two parallel pairs of nonadjacent neighbors Delete(v); Identify(w, x); Identify(y, z) let G' be the reduced graph 30

Vertex Colori ng 24. 25. 26. 27. Planar Graph s Batch Proces sing Algori thm Procedure Color(G) Color(G') Assign to each identified vertex of G the color of the vertex substituting for it in G Assign to v any color other than the at most 4 colors of the neighbors End.

31 Vertex Colori ng Planar Graph s Batch Proces sing Algori thm

Corolory 1.1: If G is a planar graph with n 3 vertices and m edges then m 3n - 6. Lemma 11: Let G = (V, E) be a planar graph with minimum degree 5, and let S be a subset of V. If every vertex of degree 5 is adjacent to at least two vertices in S, and every vertex of degree 6 is adjacent to at least one vertex in S, then |S| (n + 12)/7. Proof: Let nk denotes the number of vertices having degree k. Let V* be the set of vertices of degree greater than 6, and n* the number of such vertices Let r5 be the number of vertices of degree 5 in S r6 the number of vertices of degree 6 in S r* the number of remaining vertices in S 32 Vertex Colori ng 1. 2. Planar Graph s Batch

Proces sing Algori thm From the conditions: Note that 4. By definition we have: n5 + n6 + n* = n From corollary 1.1 we have 5. (4) 7(3): 6. Combining (1), (2) and (5): 3. 33 Vertex Colori ng

A. B. Planar Graph s Batch Proces sing Algori thm Theorem 12: The procedure Five colors a planar graph with at most five colors in O(n) time Proof: The first stage of algorithm requires at most O(n) time At the end of first stage the reduced graph G' = (V', E') contains at most 14n/17 vertices 1. 2. 3. 4. 5.

At the end of the stage, let S = {vv | Flag(v) = true, v V'} |S| n'/7 At least |S|/2 Delete and |S| identification at the stage n n' 3|S|/2 |n'| 14n/17 T (n) c1 if n 5 T(n) T(14n/17) + c2n otherwise T(n) = O(n) C. 34 Vertex Colori ng Planar Seque ntial Proces sing Algori thm It is a rather implementation of Five-Color2

It must find a vertex v of degree 5 having a pair of nonadjacent neighbors whose identification can be done in constant time: Lemma 13: let G be a planar graph of minimum degree five. Then there exists a vertex v with d(v)=5 having a pair of nonadjacent neighbors x, y such that d(x), d(y) 7. Using a data structure similar to that in batch processing algorithm one can easily implement the algorithm to run in linear time Merit: no need to any planar embedding of G 35 Vertex Colori ng Planar Graph s Seque ntial Proces sing

Algori thm Lemma 13: let G be a planar graph of minimum degree five. Then there exists a vertex v with d(v)=5 having a pair of nonadjacent neighbors x, y such that d(x), d(y) 7. Proof: G' maximal planar graph augmented from G by adding edges Desired vertex in G' will be a desired one in G For each v with d(v) = 5, let v0, v1, ..., v5 be neighbors of v listed in cyclic order Since G' is maximal planar vi and v(i+1)mod 5 are adjacent 36 Vertex Colori ng Planar Graph s Seque

ntial Proces sing Algori thm Case 1: there is no v of degree 5 such that vi and v(i+2) mod 5 are adjacent for some I Assume: G' has no desired vertex Every vertex has at most 2 (successive) neighbors of degree 7 Let v0, v1, v2 are of degree 8 D8 i 8 i.ni Each vertex of degree 5 contributes to d8 at least 5: (v, v0), (v, v1), (v, v2) , [(v0, v1), (v1, v2)] 5n5 d8 Corollary 1.3: n5 12 + i>6 (i-6)ni > i 8 i.ni/4 = d8 Contradiction 37 Vertex Colori ng Planar

Graph s Seque ntial Proces sing Algori thm Case 2: there is some vertex v of degree 5 such that (for some indexing) v2 and v4 are adjacent vv2v4 are a triangle Assume this is the innermost triangle Gv subgraph induced by vertices on and in the triangle dv = 3; dv2 , dv4 >= 3 (are adjacent to v3) All remaining vertices are of degree at least 5 Construct G8 by embedding Gv in each face of octahedral identifying vv2v4 by triangles of octahedral G8 satisfy conditions of case 1 but all vertices of octahedral are of degree 8 38 Vertex Coloring

Conjectures Hadwigers conjecture Asserts that G contains a subgraph contractible to Kn provided that (G) n H): H is an induced subgraph of as been proved for n 6 The general case remains open Hajs conjecture Asserts that every graph with (G) n contains a subdivision of Kn Catlin found a counterexample for n = 8 It is true for n 4 For n = 5, 6, 7 it remains open

39 Edge Coloring edge colorings: assign a color to each edge so that any two edges having a vertex in common have distinct colors chromatic index or edge chromatic number '(G) : The smallest possible number of colors needed for an edge coloring of a graph G. '(G) = (L(G)), where L(G) is the line graph of G '(G) (G) Holyer has shown that the edge-coloring problem is NP-hard, even if it restricted to the cubic graphs 40 Edge Coloring Bipartite Edge Chromatic Theorem 21: '(G) = (G) for bipartite graphs G. Proof: induction on the number of edges of G 1. Let G = G' (u, v) and G' edge-colored by m=(G')

colors 2. If u or v is of degree m then (G) = m + 1, we can color (u, v) by a new color m+1 3. Otherwise, if neither u nor v are incident with an edge colored with same color k, we color (u, v) by color k 4. Otherwise, there is color k not incident with u and j not incident with v 5. Let V" be set of vertices reachable from u by path in G' containing only edges colored k or j 6. E" edges colored k or j connecting two vertices of V" 41 Edge Coloring Bipartite Edge Chromatic Theorem 21: '(G) = (G) for bipartite graphs G. Proof: induction on the number of edges of G 7. Any path from u to v has odd length 8. In S = (V", E") any path from u to v must begin and end with the same color 9. v cannot be in S 10. Interchange colors in S valid coloring in G'

11. The edge incident with v are unaffected by this change 12. No edge incident with u or v colored k 13. Color (u, v) with k 42 Edge Coloring Vizings Vizings Theorem 22: Let G be a graph. Then either '(G) = (G) or '(G) = (G) + 1 Proof of inequality '(G) (G) + 1 using induction on m = |E|: 1. induction basis m = 1 is trivial. 2. choose any edge e1 = uv of G and assume that G\ e1 has already been colored using (G) + 1 colors 3. for any two colors and , let G(, ) be the subgraph of G whose edges have color or 4. connected components of G(, ): paths or cycles of even length whose edges are alternately colored with and . 5. interchanging colors and in G(, ) yields a valid coloring 6. As each vertex v has degree at most (G), there is at least one color missing at v in the coloring of G \ e1

43 Edge Coloring 7. Vizings Let M(v) be the set of missing colors at v in G\v 8. |M(u)| + |M(v1)| + (viN(u) {vv1}) |M(vi)| ((G) + 1 (d(w) 1)) + 2 + (d(w) 1) = (G) + 3 9. There is one color missed at least 2 times 44

Edge Coloring 10. 11. 12. 13. 14. Vizings If the same color is missing at u and at v1, we may assign this color to the edge e1 Now suppose color is missing at u, and color 1 is missing at v1 and some edge incident with v1 is colored with , and some edge e2 = uv2 is colored with 1 We change the given coloring as follows: we assign color 1 to edge e1 and leave edge e2 without a color for the moment If is the color missing at v2, we may color e2 with . 45 Edge Coloring 15.

16. 17. Vizings Otherwise, If u, v1, and v2 are not in the same connected component of G(, 1), we can exchange the colors and 1 in the component containing v2, so that is then missing at v2 (and is still missing at u); then we may assign to e2 Otherwise, u, v1, and v2 are in the same connected component of G(, 1), which means that there is a path from u to v2 alternately colored with and 1 This path together with the (not yet colored) edge e2 forms a cycle 46 Edge Coloring 18. 19. 20. 21. 22. Vizings

suppose that the color missing at v2 is 2 1 Assume that this color occurs at u (otherwise ...) e3 = uv3 be the edge colored with 2 We change the given coloring as follows: we assign 2 to e2 and leave e3 without a color for the moment. 47 Edge Coloring 23. 24. Vizings As before, we may assume that occurs at v3 and that u, v2, and v3 lie in the same connected component of G(, 2) (otherwise ...) there is a path from u to v3 colored alternately with and 2, and this path together with the (not yet colored) edge e3 forms a cycle 48 Edge Coloring

25. 26. 27. Vizings We continue to change the coloring in the same manner, until we reach some vertex vk adjacent to u for which the edge ek = uvk is not yet colored and one of the following two cases occurs. Case 1: some color k k1 is missing at vk, and this color is also missing at u; in this case, ek may be assigned this color. Case 2: some color i with i k 2 is missing at vk 49 Edge Coloring 28. 29. 30. 31. 32.

Vizings As before, u, vi, and vi1 are contained in the same connected component of G(, i) This component is a path P from u to vi+1 alternately colored with and i, and this path does not contain vk, since i is missing at vk component C of G(, i) containing vk is disjoint from P Now we exchange the colors and i in C then we may assign to ek to finish our coloring 50 Edge Coloring Vizings Corollary 23: Let G be a k-regular graph with n vertices. Then '(G) = k + 1 whenever n is odd. if n is even, (G) = k if and only if G admits a 1factorization (1-regular spanning subgraph). Proof: Let n be odd: n = 2i+1.

a given color can be assigned to at most i edges |E(G)| = k(2i + 1)/2 > ik '(G) > k Let n be even: n = 2i. '(G) = k iff each color is assigned to exactly i edges iff the color classes of edges form a 1-factorization. 51 Edge Coloring Vizings A k-factor is a k-regular spanning subgraph. If the edge set of a graph can be divided into k-factors, such a decomposition is called a kfactorization of the graph. A 1-factorization of K6: 52

Edge Colori ng Vizing s Theor em Algori thms Algorithm Color the algorithm Color is based on the constructive proof of Vizings theorem colors an arbitrary graph G = (V, E) with or +1 colors in O(nm) time using O(m) space 2. Algorithm Alcolor It is based on the proof of Visings adjacency lemma colors an arbitrary graph G = (V, E) with or +1 colors in O(nm) time using O(m) space edge-color a large class of graphs with d colors 1. All planar graphs with 8

All series-parallel graphs with 4 Almost all random graphs The fastest algorithms O(dm log n) O(m(n log n)1/2) 53 Edge Colori ng Vizing s Algori thm d*(w): number of vertices adjacent to w having degree an edge (v, w) is defined to be eliminable if w has at most d*(v) neighbors of degree other than v:

d*(w) + d(v) where d(v) < d*(w) = 1 where d(v) = Theorem 24: Let (v, w) be an eliminable edge and edges of G \ (v, w) colored by (G) colors. Then G can be edge-colored by (G) colors. Proof: we show that there is a color c missed at least 2 times in N(w) {vw} 54 Edge Colori ng Vizing s Algori thm Case 1: d(v) < d*(w) + d(v) w has d(w) d*(w) 1 vertices other than v each has (at least) one missing color(s) |M(w)| + |M(v)| + (viN(w) {vv})|M(vi)| ((G) (d(w) 1)) + ((G) (d(v) 1)) + (d(w) d*(w) 1) = 2 (G) +1 d(v) d*(w) 2(G) + 1 (G) = (G) +1 55 Edge Colori ng Vizing s Algori thm Case 2: d(v) = d*(w) = 1 w has d(w) 1 vertices other than v each has (at least) one missing color(s) |M(w)| + |M(v)| + (viN(u) {vv})|M(vi)| ((G) (d(w) 1)) + 1 + (d(w) 1) = (G) + 1

56 Edge Colori ng Vizing s Algori thm Procedure Alcolor(G) 1. G' G 2. while G' has an eliminable edge (v, w) and (G') = (G) 3. G' G' (v, w) 4. push (v, w) on the top of stack S 5. if((G') = (G) - 1) {vlucky case} 6. Color(G') { by (G) colors} 7. while stack is not empty 8. pop up an edge, say (v, w) from S 9.

G' G + (v, w) 10. Alrecolor(G, (v, w)) {update (G)-coloring} 11. else {unlucky case} 12. Color(G) 57 Edge Colori ng Vizing s Algori thm Lemma: Any planar graph of maximum degree>=8 has an eliminable edge. Theorem: Algorithm Alcolor edge-colors a planar graph G with d colors if d>=8. Lemma: Any series-parallel graph G (graph with no K4 as a subcontraction) whose maximum degree >= 4 has an eliminable edge Theorem: : Algorithm Alcolor edge-colors a seriesparallel graph G with d colors if d>=4 Lemma: if a series-parallel graph G with d = 3 has no

eliminable edge, then G has a triangle uvw shch that d(v)=2 and d(u) = d(w) = 3 Theorem: If a series parallel graph G is not an odd cycle, then '(G) = d Algorithm Alcolor colors almost every random graph G 58 Edge Coloring Multigraphs The best known upper bound for chromatic index '(G) (or q*(G)) of a multigraph G is given by Nishizaki and Kashiwagi: '(G) max {vp(G), 1.1 (G) + 0.8 p(G) = max H G m(H) / n(H)/2 Where H runs over all subgraphs having three or more vertices, m(H) is the number of edges in H, n(H) the number of vertices in H Since at most n(H)/2 edges of H can be colored with the same color, p(G) is a trivial lower bound on '(G) p(G) '(G) 59

Edge Colori ng Multig raphs Algori thm Multic olor Algorithm Multicolor use at most q(G) colors, where q(G) = max {vp(G), (5 (G) + 2)/4 It spends O(m( + n)) time and O(m) space Worst case ratio: maxG q(G) / '(G) = 4/3 Notes: G: multigraph which may contain multiple edges but no self-loop (v, w): an edge joining vertices v and w C(v, w): the set of colors assigned to the multiple edges joining v and w c-edge: an edge colored c M(v): set of colors not used in edges adjacent to v mis(v): a color in M(v) If G (v, w) colored with q colors, a M(v) and b M(w), then the ab-alternating path between v and w is called ab-critical path Every critical path contain an odd number of vertices

60 Edge Colori ng Multig raphs Algori thm Multic olor Procedure Multicolor(G = (V, E)) 1. if d(G) 2 2. then color G with q*(G) colors 3. else 4. q (5 (G) + 2)/4 {vcurrently available colors} 5. G' (V, )) 6. for each e in E 7.

G' G' + e 8. MultiRecolor(G', e) 9. End. Procedure MultiRecolor increase q iff q < p(G) 61 Edge Colori ng Multig raphs Algori thm Multic olor MultiRecolor(G', e) Case 1: either v and w have a common missing color of G' has no ab-critical path. Procedure APATH(e, a, b) 1. if G' has no ab-critical path then 2. interchange colors a and b of Apath(v, a, b) 3. assign a common missing color of v and w to the uncolored edge e = (v, w) 4. {vthe result is a q-coloring of G'} 62 Edge Colori ng Multig raphs Algori thm Multic olor Case 2: the ab-critical path Q = Apath(v, a, b) contains two vertices x and y having a common missing color c Procedure CPATH(e, a, b) 1. find two vertices x and y on having a common missing color c; 2. assume that v, x, y, w appear in this order 3. {vpossibly v = x or y = w} 4. While x is not followed by y in Q

5. let x' be the next vertex of x on Q 6. let c' be any missing color of x 7. interchange colors of R = Apath(x', c', c) 8. if R ends at x then x x' else y x 9. assign color c to the edge (x, y) 10. APATH(e , a, b) {vthe result is a q-coloring of G'} 63 Edge Colori ng Multig raphs Algori thm Multic olor Case 3: the ab-critical path Q contains no two vertices of a common missing color.

Q contains exactly 3 vertices: v, u, w vu is colored b, and uw is colored a H: subgraph of G' induced by u, v, w If q < m(H) = m(H) / n(H)/2 , then q < p(G) and hence we can and must introduce a new color Else, q >= m(H) There is a color c not used in H We change the coloring such that in the resulting coloring: There is no bc-critical path (back to case 1) or The bc-critical path contains at least 5 vertices (back to case 2) 64 Edge Colori ng Multig

raphs Compl exity of Appro ximati on Theorem: If P NP, there is no polynomial time approximation for edge coloring multigraphs has a worst case ratio less than 4/3 Proof: If there was such a algorithm, one can use it to decide about the chromatic index of cubic graphs. 65 Comparability and Interval Graphs Comparability Graphs Let (M, ) be a partially ordered set

G = (V, E) V =M E = {{x, y} | x y or y x} is called a comparability graph A graph G is a comparability graph if and only if it has a transitive orientation It is possible to check with complexity O(|V | 5/2) whether some given graph belongs to this class, and such a graph can be oriented with complexity O(|V |2) 66 Comparability and Interval Graphs Comparability Graphs Clique number (G) CqCq The

maximal cardinality of a clique in a graph G =(V, E). Clique partition number (G) CqCP The minimal number of cliques in a partition of V into cliques. Independence number (G) CqI maximal cardinality of an independent set of G Lemma 14: (G) Cq(G); I(G) CP(G); I(G) = Cq(G'); CP(G) = (G'). 67 Comparability and Interval

Graphs Comparability Graphs Theorem 15: Let G be a comparability graph or the complement of such a graph. Then I(G) = CP(G) And Cq(G) = (G) 68 Comparability and Interval Graphs Interval Graph Let M1, . . . , Mn be intervals of real numbers, and G the graph on {1, . . . , n} whose edges are precisely the sets {i, j} with Mi Mj = . Such a graph is called an interval graph. Lemma 16: Every interval graph is the complement of a comparability graph.

Application: coloring of an interval graph Exercise: Every interval graph is chordal (or triangulated) Every chordal graph whose complement is a comparability graph has to be an interval graph 69 Comparability and Interval Graphs Interval Graph A graph G is a comparability graph if and only if every closed trail (not necessarily a cycle) (v0, v1, ..., v2n, v2n+1 = v0) of odd length has a chord of the form vivi+2 Corollary 17: Let G be an interval graph or the complement of such a graph. Then I(G) = CP(G) and Cq(G) = (G) Example: where the intervals are time

intervals needed for performing certain tasks. A coloring of such a graph with as few colors as possible corresponds to an optimal assignment of the given set of jobs to the minimum possible number of workers (or teams) 70 Comparability and Interval Graphs Perfect Graphs A graph G is called perfect if for every induced subgraph H): H is an induced subgraph of of G: I(H): H is an induced subgraph of ) = CP(H): H is an induced subgraph of ) Or equivalently: Cq(H): H is an induced subgraph of ) = (H): H is an induced subgraph of ) Result 18: complement of perfect graph is prefect Theorem 19: Comparability graphs, interval graphs, and the complements of such graphs are perfect. Exercise: Show that bipartite graphs are perfect.

71 Comparability and Interval Graphs Perfect Graphs Theorem 20: every chordal graph is perfect Strong perfect graph theorem 21: A graph is perfect iff neither G nor G' contain a cycle of odd length 5 as an induced subgraph. Note: determining I, CP, Cq, and is an NPhard problem for graphs in general. However, all these parameters can be found in polynomial time for perfect graphs. 72 Be Happy! 73

Recently Viewed Presentations

• The first tribal college herbarium is the Navajo Nation Herbarium, which was established in 2003 and is currently the only tribal college herbarium to be listed in the Index Herbariorum (The Navajo Nation, n.d.). Development
• 8th Grade DOLS. DOL #1. ladies and gentlemen. please send me the following coins two wooden nickels one five dollar gold piece and three jefferson nickels. sincerely. ericcameron. DOL #2. us girls havent never tore that paper into peices.
• Expect to publish VAT Notice in early summer . MTD VAT Legislation | Adjustments. This could be a spreadsheet. Adjustment by manual intervention . This could range from correcting mistakes to adjustments required by VAT law. Could take place within...
• Cycle day [length of shortest cycle - 18] toCycle day [length or longest cycle - 11] ... Once fertilization had taken place, EC did not prevent establishment of pregnancy . 1. Human: LNG administered during luteul phase did not cause...
• 7.2.1 The PA/TA and Formal Transport. PA/TA's responsibilities in regard to formal public transport as follows:. to determine which routes and schedules should be operated. to grant concessions and contracts to operators of rail, bus and minibus-taxi services to operate...
• To better serve CFAS representatives with programming, products, and services, a survey was sent to all CFAS reps in the spring of 2018 to gather detailed demographic data on the council's members.
• AODA Prevention Partnership May 8, 2013 University of Wisconsin-Stevens Point Agenda Welcome from your Co-Chairs Responsible Action legislation by SGA Alcohol-Wise Findings Preliminary AODA Survey Findings Online Program Options Sanction Grid Strategic Planning Process Next full Prevention Partnership meeting, November...
• Bundle High Speed Internet in Ontario and Quebec with ACN DigitalTalk®Express Customers get one bill, one service provider and one number to call. Competitively priced and can save business more