Report

Graph Coloring David Laughon CS594 Graph Theory Definitions • Coloring – Assignment of labels to vertices f :V(G) ® S • k-coloring – a coloring where S =k • Proper k-coloring – k-coloring where vertices have different labels if they are adjacent • Chromatic number – least k for which G is k-colorable - χ(G) Definitions • A Graph is k-chromatic if χ(G) = k • Optimal coloring – proper k-coloring of a k-chromatic graph – Vertex-coloring problems • Is a graph k-colorable for given k? • What is χ(G) / what is the optimal coloring? History • Four-color conjecture – Francis Guthrie, 1852 (F.G.) – Can any map be colored using at most 4 colors so that adjacent regions are not the same color? • Many incomplete proofs (Kempe) – “Counterexamples” • 5-color theorem proved in 1890 (Heawood) • 4-color theorem finally proved in 1977 (Appel, Haken) – First major computer-based proof • Graph coloring applies to non-planar graphs as well 4-color “Counterexample” • Martin Gardner, April 1975 edition of Scientific American • As an April fool’s joke, claimed graph required 5 colors Examples Proper 6-coloring Optimal 4-coloring Examples – Kn • For complete graphs, χ(G) = n • Each vertex has n-1 edges that connect to every other vertex – Forces each vertex to have a unique color Examples • A graph is 2-colorable iff it is bipartite Examples • ω(G) – size of largest clique in G • χ(G) ≥ ω(G) – Clique of size n requires n colors – Can be a tight bound, but not always Examples χ(G) = 7, ω(G) = 5 Examples • Mycielski’s Construction – Can be used to make graphs with arbitrarily large chromatic numbers, that do not contain K3 as a subgraph Greedy Coloring • χ(G) ≤ Δ(G) + 1 • Greedy Algorithm: – Put the vertices of a graph in a sequence – For each vertex in the sequence, assign it the lowest indexed color not already assigned to adjacent vertices • Not guaranteed to be optimal for every possible sequence • Guaranteed optimal for at least one sequence Greedy Coloring Example Vertex 0 1 2 3 4 5 Color Yellow Yellow Yellow Green Green Green Greedy Coloring Example Vertex 0 3 1 4 2 5 Color Yellow Yellow Green Green Purple Purple Kempe Chains • A path in a graph that alternates between 2 colors • First used by Kempe in his incorrect proof of the 4-color theorem • Used in 5-color theorem and 4color theorem proofs 5-color theorem • All planar graphs can be colored with at most 5 colors • • • • Basis step: True for n(G) ≤ 5 Induction step: n(g) > 5 There exists a vertex v in G of degree at most 5 (Theorem 6.1.23) G – v must be 5-colorable by induction hypothesis 5-color Theorem • If G is 5-colorable, done • If G is not 5 colorable, we have: • Is there a Kempe chain including v1 and v3? 5-color Theorem There is no Kempe chain There is a Kempe chain 5-color Theorem There cannot be a Kempe chain including v2 and v4 v4 cannot directly influence v2 Edge Coloring • Similar to vertex coloring, except edges are colored – Adjacent edges have different colors Edge Coloring • Every edge-coloring problem can be transformed into a vertexcoloring problem • Coloring the edges of graph G is the same as coloring the vertices in L(G) • Not every vertex-coloring problem can be transformed tin an edgecoloring problem – Every graph has a line graph, but not every graph is a line graph of some other graph Edge Coloring K4 edge-coloring L(K4) vertex-coloring Multi-coloring • Each vertex in G has a positive integer label x(v): the number of colors that must be assigned to that vertex • The color sets of adjacent vertices must be disjoint χ(G) = 5 {Blue} {Yellow, Green, Purple, Red} {Yellow, Green} {Blue} Multi-coloring • Every multi-coloring problem can be transformed to a vertexcoloring problem – For each vertex with x(v) = n, replace it with a clique of size n. – Add an edge from each vertex in the new clique to every vertex that the original vertex was adjacent to. – Single vertex-coloring now solves the problem Multi-coloring χ(G) = 5 Applications • • • • • • Scheduling Register allocation VLSI channel routing Biological networks (Khor) Testing printed circuit boards (Garey, Johnson, & Hing) Sudoku Applications: Sudoku • Each cell is a vertex • Each integer label is a “color” • A vertex is adjacent to another vertex if one of the following hold: – Same row – Same column – Same 3x3 grid • Vertex-coloring solves Sudoku State of the Art • • • • • • Decide if a graph is k-colorable is NP-complete Determining χ(G) is NP-hard k-colorable – O(2.445^n) (Lawler) 3-colorable – O(1.3289^n) (Beigel, Eppstein) 4-colorable – O(1.7272^n) (Fomin, Gaspers, & Saurabh) Alternative methods of solving graph coloring – Swarm intelligence (Dorrigiv, Markib) Open Problems • Hadwiger Conjecture – Every k-chromatic graph has a subgraph that becomes Kk through edge contractions – Open for k ≥ 7 Open Problems • Erdős–Faber–Lovász conjecture – Consider k complete graphs with exactly k vertices. If every pair of complete graphs shares at most one vertex, then the union of the graphs can be colored with k colors References • • • • • • • F. G. (June 10, 1854), "Tinting Maps", The Athenaeum: 726. Heawood, P. J. (1890), "Map-Colour Theorems", Quarterly Journal of Mathematics, Oxford 24: 332–338 Appel, Kenneth; Haken, Wolfgang (1977), "Every Planar Map is Four Colorable Part I. Discharging", Illinois Journal of Mathematics 21: 429–490 Appel, Kenneth; Haken, Wolfgang; Koch, John (1977), "Every Planar Map is Four Colorable Part II. Reducibility", Illinois Journal of Mathematics 21: 491–567 Appel, Kenneth; Haken, Wolfgang (October 1977), "Solution of the Four Color Map Problem", Scientific American 237 (4): 108–121 Khor, S., "Application of graph colouring to biological networks," Systems Biology, IET , vol.4, no.3, pp.185,192, May 2010 Garey, M.R.; Johnson, D.; Hing So, "An application of graph coloring to printed circuit testing," Circuits and Systems, IEEE Transactions on , vol.23, no.10, pp.591,599, Oct 1976 References • • • • Lawler, E.L. (1976), "A note on the complexity of the chromatic number problem", Information Processing Letters 5 (3): 66–67 Beigel, R.; Eppstein, D. (2005), "3-coloring in time O(1.3289n)", Journal of Algorithms 54 (2)): 168–204 Fomin, F.V.; Gaspers, S.; Saurabh, S. (2007), "Improved Exact Algorithms for Counting 3- and 4-Colorings", Proc. 13th Annual International Conference, COCOON 2007, Lecture Notes in Computer Science 4598, Springer, pp. 65–74 Dorrigiv, M.; Markib, H.Y., "Algorithms for the graph coloring problem based on swarm intelligence," Artificial Intelligence and Signal Processing (AISP), 2012 16th CSI International Symposium on , vol., no., pp.473,478, 2-3 May 2012 Homework • Prove that every graph has a vertex ordering such that the greedy coloring algorithm produces an optimal coloring • Given a k-chromatic graph and an optimal coloring of it, prove that for each color i there is a vertex with color i that is adjacent to vertices of all the other k-1 colors