Coloring
Chromatic number, motivated by a map-coloring puzzle, and bounds on how few colors a graph can need.
3 exercises
Exercise 1
What is the smallest number of colors you need to properly color the vertices of ? That is, find the chromatic number of the graph.
Exercise 2
Draw a graph with chromatic number 6 (i.e., which requires 6 colors to properly color the vertices). Could your graph be planar? Explain.
Exercise 12
You have a set of magnetic alphabet letters (one of each of the 26 letters in the alphabet) that you need to put into boxes. For obvious reasons, you don't want to put two consecutive letters in the same box. What is the fewest number of boxes you need (assuming the boxes are able to hold as many letters as they need to)?
Adapted from Discrete Mathematics: An Open Introduction © 2013–2019 Oscar Levin. Licensed under CC BY-SA 4.0. Source: Discrete Mathematics: An Open Introduction. Imported at revision 1e2e26b.