Report

Graph Coloring prepared and Instructed by Shmuel Wimer Eng. Faculty, Bar-Ilan University March 2014 Graph Coloring 1 Vertex Coloring A k-coloring of a graph G is a labeling f : V(G) → { 1,…,k }. A coloring is proper if no two vertices x and y, connected with an edge have same color, xy ϵ E(G) => f(x) ≠ f(y). G is k-colorable if it has proper k-coloring. The chromatic number χ(G) is the smallest k such that G has proper k-coloring. G is called k-chromatic. If χ(G) = k, but χ(H) < k for every proper subgraph H, then G is k-critical. March 2014 Graph Coloring 2 The vertices having same color in a proper k-coloring must be independent. Therefore, χ(G) is the minimum number of independent sets covering G. Hence, G is k-colorable iff G is k-partite. Examples. Every bipartite graph is 2-colorable. Every even cycle graph is 2-colorable (it is bipartite). Every odd cycle graph is 3-colorable and 3-critical. 2-colorability can be tested with BFS. (how?) We compute the distance from a vertex u. A connected graph is bipartite iff G[X] and G[Y] are independent sets, where X and Y are vertices of even and odd distance from u, respectively. March 2014 Graph Coloring 3 The largest clique size ω(G) satisfies χ(G) ≥ ω(G). The largest independent set size α(G) satisfies χ(G) ≥ n(G) / α(G). Is it possible that χ(G) > ω(G)? s Yes, χ(G) may exceed ω(G)! Proper coloring of Ks requites s colors. G s s C5 s s Ks+2 Ks Ks with any two adjacent of C5 vertices turn into Ks+2. χ(G) = s+3 whereas ω(G) = s+2! Hence χ(G) > ω(G). Could it be constructed with C3 rather than C5? March 2014 Graph Coloring 4 Upper Bounds of Chromatic Number Easy bounds are χ(G) ≤ n(G), χ(G) ≥ ω(G), and χ(G) ≥ n(G) / α(G), all hold with equality for cliques. Better than χ(G) ≤ n(G) upper bounds can be obtained by coloring algorithms. A greedy algorithm w.r.t V(G) order v1,…,vn , assigns to vi the smallest color index not incident so far to vi. Proposition. There is χ(G) ≤ ∆(G) + 1. (∆(G) is the largest vertex degree.) Proof. By construction. A vertex has no more than ∆(G) neighbors. Upon vi coloring there must be at least one of 1,…, ∆(G)+1 colors unused. ■ March 2014 Graph Coloring 5 Different orderings may yield smaller upper bounds. Finding the best ordering is hard. Is there an ordering yielding χ(G)? It can be shown that such one exists. Example. Register allocation and interval graphs. Consider the registers used by a compiler, each has start and end time. What is the smallest number of physical registers that can be used? Assign the symbols a, b, c, … to the registers in the code, and draw their usage time intervals. a b f c d e g Proposition. If G is an interval graph then χ(G) = ω(G). March 2014 Graph Coloring 6 Proof. By left-to-right traversal of the time intervals, pre sorted by their starting time. Initializing k=0. Increasing to k+1 at starting point and decreasing to k-1 at ending point. ■ The bound χ(G) ≤ ∆(G)+1 may still be very poor. For (n+1)-vertex star graph ∆(G) = n, whereas χ(G) = 2. For (n+1)-vertex wheel graph ∆(G) = n, whereas χ(G) ≤ 4. March 2014 Graph Coloring 7 The bound χ(G) ≤ ∆(G)+1 can be further improved by considering the vertices with high degree first. Proposition. (Welsh-Powell 1967) If the vertices are ordered in non increasing degree, d1 ≥ d2 ≥ … dn, then χ(G) ≤ 1 + maxi min { di , i-1 }. Proof. When vertex i is colored, at most min { di , i-1 } of its neighbors have already been colored. Its color is therefore 1 + min{ di , i-1 }. Maximization over i yields the upper bound. ■ The minimum degree δ(G) in G can also be used to deduce upper bounds. March 2014 Graph Coloring 8 Lemma. If H is k-critical graph, then δ(H) ≥ k-1. Proof. Assume in contrary that δ(H) < k-1. Let x ϵ H be any vertex. Since H is k-critical, H-x is (k-1)-colorable. If dH(x) < k-1, then not all the k-1 colors used in H-x are used for N(x). We could therefore drop one of the missing colors for x. That holds for any x. By color renaming we can obtain a proper k-1 coloring of H, hence a contradiction. ■ March 2014 Graph Coloring 9 Corollary. (Szekeres-Wilf 1968) G 1 m ax H G H . Proof. Let k G and H’ be a k-critical subgraph of G. By the above lemma H k 1 G 1 . There is also bound. ■ March 2014 H m ax H G H Graph Coloring , yielding the desired 10 Coloring of Directed Graphs Theorem. Let a graph G be directed with longest path l(G), then χ(G) ≤ 1 + l(G). Furthermore, there are orientations of G’s edges such that equality holds. 2 G 4 3 1 5 G’ 6 1 Proof. Let G’ be a maximal acyclic sub digraph of G (not necessarily a tree). G’ must have vertices with outgoing arcs only. Define f(v) to be a coloring function assigning color 1+l(v). March 2014 Graph Coloring 11 f is strictly increasing along a path in G’ using colors 1+l(G’) on V(G) = V(G’). For each edge uv ϵ E(G) there exists a path in G’ between u and v, since either there was uv ϵ E(G’) or the edge is closing a cycle of G. That implies f(u) ≠ f(v) since f increases along paths of G’. Consequently, f is a proper coloring and χ(G) ≤ 1 + l(G). To show orientations of G’s edges satisfying χ(G) = 1 + l(G), an orientation satisfying χ(G) ≥ 1 + l(G) is shown. March 2014 Graph Coloring 12 Let f be an optimal coloring satisfying f(G) = χ(G). We derive digraph G* as follows. Each edge uv ϵ E(G*) is oriented u → v iff f(u) < f(v). Since f is a proper coloring, this defines an orientation. Since the color labels along paths in G* strictly increase, and there are only χ(G) labels, there is l(G*) ≤ χ(G*) – 1, hence χ(G) = 1 + l(G). ■ March 2014 1 2 G G* 4 Graph Coloring 3 13 Brook’s Theorem The bound χ(G) ≤ ∆(G) + 1 holds for any graph. Brook showed that cliques and odd cycles are essentially the only graphs where χ(G) = ∆(G) + 1 holds. Theorem. (Brook 1941) If G is connected and other than a clique or an odd cycle, then χ(G) ≤ ∆(G). Proof. Let G have n nodes and be connected, neither a clique, nor an odd cycle. Let k = ∆(G) and assume k ≥ 3, as otherwise for k = 1 it is a clique, and bipartite or an odd cycle for k = 2. Consider first the case where G is not k-regular. Choose a vertex vn for which d(vn) < k and grow a spanning tree rooted at vn (by any search). March 2014 Graph Coloring 14 Index the vertices in decreasing order as they are being reached by the search, yielding the order v1, v2, … ,vn. Each vertex other than vn has a higher-indexed neighbor along its path to root, hence it has at most k-1 lowerindexed neighbors. Using the greedy coloring with the vertex decreasing order obtains proper k-coloring. In the remaining cases G is k-regular. 1st case: G is 1-connected. Let x be a cut-vertex. Let G’ be a component of G-x together with x. The degree of x in G’ is less than k and a proper k-coloring is possible. March 2014 Graph Coloring 15 G’ x G This can be repeated for every components of G-x, yielding k-proper coloring for each (x included). By permuting colors within the subgraphs, we can make the colorings agree on x, yielding k-proper coloring of G. 2nd case: G is not 2-connected. Find a vertex vn with neighbors v1 and v2 (non adjacent ) whose deletion leaves a connected subgraph. March 2014 Graph Coloring 16 v1 v2 vn G - {v1 , v2 } is connected and a spanning tree rooted at vn can be constructed. The labels 3 , … , n are assigned to the vertices in decreasing order as they are reached. Starting coloring from v1 and v2, they use same color. Then, each vertex other than vn has at most k-1 lowerindexed neighbors and k colors can be used for those. March 2014 Graph Coloring 17 vn has k neighbors, of which v1 and v2 already used the same color. The rest neighbors used at most other k-2 colors, and vn can therefore be properly colored. All in all, k proper coloring of G has been obtained. 3rd case: G is 2-connected. Choose a vertex x such that vertex connectivity κ(G-x) = 1. x = vn March 2014 Graph Coloring 18 v1 v2 x = vn x has a neighbor in every block of G-x obtained by deleting the 2nd vertex in a cut-set, else G is 1-connected rather than 2-connected. There is no edge connecting v1 and v2 since they are in different blocks. G - {x , v1 , v2 } is connected since blocks have no cutvertices and v1 , v2 are no such. March 2014 Graph Coloring 19 k ≥ 3 implies G - {v1 , v2 } is also connected. All in all this is the same situation as the case of G not 2connected. ■ Brook’s Theorem implies that the cliques and the odd cycles are the only (k-1)-regular k-critical graphs. (homework) March 2014 Graph Coloring 20 Chromatic Polynomials We shall associate with any graph a function telling whether or not it is 4-colorable. This study was motivated by the hope to prove the FourColor Theorem, which by that time was a conjecture. Let PG(k) denote the number of proper colorings of a graph G with k colors. PG(k) is called the chromatic function of G. Example. PG(k) = k (k - 1)2. The first vertex can be colored in k ways, while each of the other two in k-1 ways. For a tree T of n vertices there is PT(k) = k (k - 1)n-1. March 2014 Graph Coloring 21 For G = K3 there is PG(k) = k (k - 1) (k - 2) and for G = Kn there is PG(k) = k (k - 1) (k - 2) · · · (k – n + 1). If k < χ(G) then PG(k) = 0. For k ≥ χ(G) there is PG(k) > 0. The Four-Color Theorem for planar graph G is equivalent to the statement that PG(4) > 0. It is difficult to compute PG(k) by inspection, but it can be systematically obtained as a sum of chromatic functions of complete graphs. Theorem. Let u,v ϵ V(G) be not incident, G1 be obtained by adding the edge uv to G, and G2 be obtained by identifying u and v in G. Then PG(k) = PG1(k) + PG2(k). March 2014 Graph Coloring 22 u v v G1 G k(k-1)(k-2)2 u = uv G2 k(k-1)(k-2)(k-3) + k(k-1)(k-2 Proof. In a proper coloring of G, u and v may have either the same color or different colors. The number of proper colorings where u and v have different colors does not change if an edge uv would exist, yielding PG1(k). March 2014 Graph Coloring 23 Similarly, the number of proper colorings where u and v have same color does not change if an u and v are merged, yielding PG2(k). ■ Corollary. The chromatic function is a polynomial. Proof. The procedure of the theorem results in two graphs. In G1 the number of edges is increased. In G2 the number of vertices is decreased. The process is finite. It ends with producing complete graphs, whose chromatic functions are polynomial. The chromatic function is therefore a finite sum of polynomials, which must be polynomial too. ■ March 2014 Graph Coloring 24 For n-vertex graph G the degree of PG(k) is n, the coefficient of kn is 1 and that of kn-1 is |E(G)|, the sign of the coefficients is alternating, and the free coefficient is zero. Example. PG(k) = k5 - 7k4 + ak3 - bk2 + ck w v w = + w v March 2014 v Graph Coloring 25 v v + = w = + + + w +2 + PG(k) = k(k - 1)(k - 2)(k - 3)(k - 4) + 3k(k - 1)(k - 2)(k - 3) + 2k(k - 1)(k - 2) = k5 - 7k4 + 19k3 - 23k2 + 10k March 2014 Graph Coloring 26 Example: Scheduling feasibility. A schedule for certain lectures is required, for which some time slots are given (e.g., campus is open). There is no limit of available rooms. It is known that some lectures cannot take place in parallel (e.g. students are registered to both). Is scheduling feasible? How many schedules there are? Solution. Define a graph where lectures are vertices and edges correspond to lectures that cannot be scheduled at the same time slot. The chromatic polynomial, where k is the number of time slots answer the questions. ■ March 2014 Graph Coloring 27 Edge Coloring A k-edge-coloring of a graph G is a labeling f : E(G) → { 1, … ,k }. Edge coloring partitions E(G) into k sets (some possibly empty) { E1, E2, … , Ek }. An edge coloring is proper if adjacent edges have different colors. All coloring henceforth are meant to be proper. Edge coloring thus partitions E(G) into k sets { M1, M2, … , Mk } of matchings. (Only loopless graphs admit proper edge coloring). March 2014 Graph Coloring 28 G is k-edge-colorable if it has k-edge-coloring. Clearly, G is m-edge-colorable, where m = |E(G)|. The edge chromatic number is the smallest k such that G has k-edge-coloring. G is called k-edge-chromatic. Not 3-edge-colorable, hence χ’(G) = 4. Clearly, χ’(G) ≥ Δ(G). Example. (Timetabling) m teachers x1, x2, … , xm and n classes y1, y2, … , yn are given. Teacher xi is required to teach class yj a lessen of period pij. Schedule a complete timetable having minimum duration. March 2014 Graph Coloring 29 Solution. The scheduling is represented by a bipartite graph H[X,Y], X = { x1, x2, … , xm } , Y = { y1, y2, … , yn } vertices xi and yj are connected with pij parallel edges. The minimum number of colors required for H edgecoloring ensures minimum duration. • No schedule overlap for a teacher. • No two lesson schedules overlap in a class. ■ March 2014 Graph Coloring 30 Edge Coloring of Bipartite Graphs Let the subgraph H span G (V(H) = V(G)), and C := { M1, M2, … , Mk } be a k-edge-coloring of H. A color is available for an e ϵ E(G) \ E(H) if it is available in its two end vertices. If e is uncolored, any of its available colors can be assigned to extend C to a k-edge-coloring of H + e. For i ≠ j , each component of Hij := H[Mi U Mj] is either an even cycle or a path (called ij-path). (why?) Theorem. If G is bipartite then χ’(G) = Δ(G). March 2014 Graph Coloring 31 Proof. By induction on m = |E(G)|. Let e = uv ϵ E(G). Assume that H = G \ e has a Δ-edge-coloring { M1, M2, … , MΔ }. If a color is available for e we are done. Otherwise, each of the Δ colors is represented either at u or at v. Since the degrees of u and v in G \ e are Δ-1 at most, there are colors i ≠ j, where i is available at u and exists in v, and j is available at v and exists in u. Consider the subgraph Hij := H[Mi U Mj]. Because u has a degree one in Hij, the component containing u is an ijpath P. March 2014 Graph Coloring 32 P cannot terminate at v. If it did, it would started from u with color j and end at v with color i, hence comprising even number of edges. u P P + e would then be an odd cycle in G, impossible for a bipartite graph. v Interchanging the colors of u P e P, a new Δ-edge-colorable H is obtained, where color j is available at u and v. v Assigning color j to e obtains a Δ-edge-coloring of G. ■ March 2014 Graph Coloring 33 Clearly, there is χ’(G) ≥ Δ(G), and for bipartite graphs there is χ’(G) = Δ(G). What can be said about an upper bound? Surprisingly, it is very tight. Theorem. (Vizing 1964, Gupta 1966). Let G be a simple (no parallel edges, loopless) graph. Then χ’(G) ≤ Δ(G) + 1. Proof. Let G’, a proper subgraph of G, be edge-colored with Δ(G) + 1 colors, but uv could not be colored. We present a recoloring procedure to include uv. Since more than Δ(G) colors are used, every vertex has a color not presented. Let a0 be missing from u and a1 from v. (a0 must be presented at v and a1 at u.) March 2014 Graph Coloring u v 34 Let v1 be neighbor of u along the edge colored a1. At v1 some color a2 must be missing. Suppose a2 does not appear on u. We could recolor uv1 with a2, free a1 from u, and then color uv with a1. u v1 v u v So we suppose that a2 appears on u. v1 The process continues for i ≥ 2. Finding a new color ai that appears at u, let vi be the neighbor of u along the edge colored ai. March 2014 Graph Coloring 35 At vi some color ai+1 must be missing. If ai+1 is missing at u, we downshift color aj from uvj to uvj-1 for 1 ≤ j ≤ i (uv0 = uv). vi ai+1 v2 u v1 v vi vi ai+1 ai+1 v2 u v1 v v2 u v1 v We are finished, unless ai+1 appears at u, in which case the process continues. There are only Δ(G) + 1 colors, hence the iterative selection of ai+1 eventually repeats a color. March 2014 Graph Coloring 36 Let a1 , … , al be the shortest non repetitive color list such that al+1 is missing at vl and repeats one of a1 , … , al-1 . Let al+1 = ak for some 1 ≤ k ≤ l-1. This color is missing from vk-1 and appears on uvk. vk-1 If vl lacks a0 , we downshift colors from vl and use a0 on uvl to complete the augmentation. v2 vk P vl u v1 v Hence we assume that a0 appears at vl and ak does not. Let P be the longest alternating path of edges colored a0 and ak that begins at vl (with a0). March 2014 Graph Coloring 37 P is unique. (why?) Depending on the opposite end of P, recoloring can take place to complete the augmentation. Three possibilities exist: P ends at vk, P ends at vk-1, and P ends elsewhere. If P ends at vk, it is with a0 since uvk is colored with ak. Downshifting from vk, switching colors of P, and coloring uvk with a0 , completes the augmentation. March 2014 a0 ak vk-1 a0 vk ak a0 vl ak vk-1 u v2 v1 Graph Coloring vk ak vl a0 u v v2 v1 v 38 If P ends at vk-1, it is with a0 since vk-1 lacked ak. Downshifting from vk-1, switching colors of P, and coloring uvk-1 with a0 , completes the augmentation. ak a0 vk-1 v2 vk a0 a0 vl ak u v1 v ak vk-1 v2 vk ak vl ak u v1 v Finally, suppose that P neither reaches vk nor vk-1, so it ends at some vertex outside { u , vl , vk , vk-1 } March 2014 Graph Coloring 39 P terminates with a0 (ak) colored edge, a case were the far end vertex lacks ak (a0). (The vertices along P can also touch any of u neighbors N(u) - {vk , vk-1 }, as a0 assumed presented at those.) We downshift from vl , give color a0 to uvl , and switch colors of P. ■ P a0 ak v k-1 v2 March 2014 ak vk P ak a0 vl ak a0 v k-1 u v1 v2 v Graph Coloring a0 vk ak vl ak u v1 v 40 Line Graphs Many questions about vertices have natural analogues involving edges. Independent sets have no pairs of adjacent vertices; matchings have no adjacent edges. Vertex coloring partitions the vertices into independent sets; edges can instead be partitioned into matchings. Definition. The line graph L(G) is defined by V(L(G)) ≡ E(G) and ef ϵ E(L(G)) if e = uv and f = vw , where u,v,w ϵ V(G). March 2014 Graph Coloring w G u f e v h g f L(G) e h g 41 Line Graphs Characterization Theorem. (Krausz 1943) A simple graph G is the line graph of some simple graph iff E(G) has a partition into cliques using each vertex of G at most twice. Proof. Denote by H the original graph. Necessity follows from the fact that the edges adjacent at a vertex of H are represented in L(H) by vertices connected in a clique. Since an edge connects two vertices, those vertices imply two cliques at most. March 2014 cliques in L(H) N(u) u v N(v) vertex in L(H) Graph Coloring 42 For sufficiency, suppose E(G) has such a partition, using cliques { S1 , … , Sk }. We shall construct H satisfying G = L(H). Assume that G has no isolated varices. Let v1 , … , vl be the vertices of G (if any) that appear in a single clique of { Si }. We define a vertex in H for each set of A = S1 , … , Sk , { v1 }, … , { vl }. Edges of H are defined such that H vertices are adjacent if the corresponding sets of A intersect. Each vertex of G appears exactly in two sets of A. Also, two vertices cannot both appear in two sets of A, as otherwise a clique was split among the sets. March 2014 Graph Coloring 43 impossible clique G = L(H) => H clique Hence there are no parallel edges in H, so it is simple, and there is one edge in H for each vertex of G. Adjacent vertices in G appear together in some Si and the corresponding edges of H share the vertex corresponding to Si. Hence G = L(H). ■ The above theorem does not directly yield an efficient test for line graph, which the following does. March 2014 Graph Coloring 44 Theorem. (Bieneke 1968) A simple graph G is the line graph of some simple graph iff G does not contain any of the following subgraphs as an induced subgraph. March 2014 Graph Coloring 45