Graph ColoringIntroductionSlide 3Dual Graph ExamplesSlide 5ExampleSlide 7ApplicationsCS 2813 Discrete StructuresGraph ColoringCS 2813 Discrete StructuresIntroduction•When a map is colored, two regions with a common border are customarily assigned different colors.•We want to use a small amount of colors instead of just assigning every region its own color.CS 2813 Discrete StructuresGraph Coloring•Each map in a plane can be represented by a graph.–Each region is represented by a vertex.–Edges connect to vertices if the regions represented by these vertices have a common border.–Two regions that touch at only one point are not considered adjacent.•The resulting graph is called the dual graph of the map.CS 2813 Discrete StructuresDual Graph ExamplesABCDEFGABCDE B A E DC C B A D F G ECS 2813 Discrete StructuresGraph Coloring•A coloring of a simple graph is the assignment of a color to each vertex of the graph so that no two adjacent vertices are assigned the same color.•The chromatic number of a graph is the least number of colors needed for a coloring of the graph.•The Four Color Theorem: The chromatic number of a planar graph is no greater than four.CS 2813 Discrete StructuresdExample b ea d g c fThe chromatic number must beat least 3 since a, b, and c mustbe assigned different colors. So lets try 3 colors first. ba c3 colors work, so the chromatic number of this graph is 3.•What is the chromatic number of the graph shown below? efgCS 2813 Discrete StructuresExample•What is the chromatic number for each graph?WhiteYellowWhiteYellowWhiteYellowChromatic number: 2WhiteYellowWhiteYellowGreenChromatic number: 3CS 2813 Discrete StructuresApplications•Scheduling Final Exams•How would you model this with a graph?•After you have drawn a graph, what should you
View Full Document
![23FL20heap[1]](https://media.gradebuddy.com/documents/68167/f5ba0121-bfeb-4bce-8c70-9325cd50ffaf.png)
Unlocking...