# David Laughon CS594 Graph Theory Graph Coloring. Coloring – Assignment of labels to vertices k-coloring – a coloring where Proper k-coloring – k-coloring.

• Published on
17-Dec-2015

• View
224

10

Transcript

• Slide 1
• David Laughon CS594 Graph Theory Graph Coloring
• Slide 2
• Coloring Assignment of labels to vertices k-coloring a coloring where 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
• Slide 3
• 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? Definitions
• Slide 4
• 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 History
• Slide 5
• Martin Gardner, April 1975 edition of Scientific American As an April fools joke, claimed graph required 5 colors 4-color Counterexample
• Slide 6
• Proper 6-coloringOptimal 4-coloring Examples
• Slide 7
• 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 K n
• Slide 8
• A graph is 2-colorable iff it is bipartite Examples
• Slide 9
• (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
• Slide 10
• (G) = 7, (G) = 5
• Slide 11
• Mycielskis Construction Can be used to make graphs with arbitrarily large chromatic numbers, that do not contain K 3 as a subgraph Examples
• Slide 12
• (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
• Slide 13
• Vertex012345 ColorYellow Green Greedy Coloring Example
• Slide 14
• Vertex031425 ColorYellow Green Purple Greedy Coloring Example
• Slide 15
• 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 4- color theorem proofs Kempe Chains
• Slide 16
• 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
• Slide 17
• 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
• Slide 18
• There is no Kempe chainThere is a Kempe chain 5-color Theorem
• Slide 19
• There cannot be a Kempe chain including v2 and v4 v4 cannot directly influence v2 5-color Theorem
• Slide 20
• Similar to vertex coloring, except edges are colored Adjacent edges have different colors Edge Coloring
• Slide 21
• Every edge-coloring problem can be transformed into a vertex- coloring 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 edge- coloring problem Every graph has a line graph, but not every graph is a line graph of some other graph Edge Coloring
• Slide 22
• K 4 edge-coloringL(K 4 ) vertex-coloring Edge Coloring
• Slide 23
• 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 Multi-coloring {Yellow, Green, Purple, Red} {Blue} {Yellow, Green} {Blue} (G) = 5
• Slide 24
• Every multi-coloring problem can be transformed to a vertex- coloring 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
• Slide 25
• (G) = 5
• Slide 26
• Scheduling Register allocation VLSI channel routing Biological networks (Khor) Testing printed circuit boards (Garey, Johnson, & Hing) Sudoku Applications
• Slide 27
• 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 Applications: Sudoku
• Slide 28
• 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) State of the Art
• Slide 29
• Hadwiger Conjecture Every k-chromatic graph has a subgraph that becomes K k through edge contractions Open for k 7 Open Problems
• Slide 30
• ErdsFaberLovsz 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 Open Problems
• Slide 31
• F. G. (June 10, 1854), "Tinting Maps", The Athenaeum: 726."Tinting Maps"The Athenaeum Heawood, P. J. (1890), "Map-Colour Theorems", Quarterly Journal of Mathematics, Oxford 24: 332338 Heawood, P. J. Appel, Kenneth; Haken, Wolfgang (1977), "Every Planar Map is Four Colorable Part I. Discharging", Illinois Journal of Mathematics 21: 429490 Appel, Kenneth; Haken, Wolfgang; Koch, John (1977), "Every Planar Map is Four Colorable Part II. Reducibility", Illinois Journal of Mathematics 21: 491567 Appel, Kenneth; Haken, Wolfgang (October 1977), "Solution of the Four Color Map Problem", Scientific American 237 (4): 108121 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
• Slide 32
• Lawler, E.L. (1976), "A note on the complexity of the chromatic number problem", Information Processing Letters 5 (3): 6667 Lawler, E.L. Information Processing Letters Beigel, R.; Eppstein, D. (2005), "3-coloring in time O(1.3289 n )", Journal of Algorithms 54 (2)): 168204Eppstein, D.Journal of Algorithms 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. 6574Lecture Notes in Computer Science 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 References
• Slide 33
• 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 Homework