MAT344H1 Lecture 6: Coloring
Document Summary
Def: a k-coloring of g is the assignment of one of k colors to each vertex s. t. adjacent vertices can give distinct color. Want to give times for sports s. t. no conflicts arise. Recall: any planar graph can be 4-colored (proved in 1976 by some dude) Note: a graph non-planar can need greater than 4 colors has no 4-coloring, it needs 5 colors. Theorem: any planar graph can be 5 colored (easier to prove them 4 colored, not a sharp bound) First we need an easy lemma, follows from euler"s theorem on planar graphs: any planar graph (non-empty) contains vertex v of degree less than or equal to 5 (exercise in textbook 1. 4) Use induction on number of vertices to prove theorem. Let v in g have deg <= 5. To get 5 coloring of g, need a color for v. In the graph at the right, try to change 1 to 3.
