Graph Coloring

  1. You are given the following figure and asked to color it in with the colors red, blue, green, and purple. The only restriction is that no two squares of the same color can touch along a sidelength. How many color combinations are possible?Screen Shot 2019-06-11 at 11.23.02 AMColor Example 1
  2. Does your answer to question 1 change if you are restricted to only red, blue, and green as color options? What about just red and blue?
  3. Once again, you are allowed to use green, blue, red, and purple, but now you are trying to color in the figure below. How many color combinations are there?Screen Shot 2019-06-11 at 11.33.30 AM
  4. Going back to question 1, what is the minimum number of colors you need? What about the maximum?
  5. Let’s say you have the image below. What is the maximum number of colors you need? The minimum? If you are restricted to red, blue, green, and purple, how many coloring possibilities are there?Screen Shot 2019-06-11 at 11.38.53 AM.png
  6. Using the image from problem 5, you are allowed to use red, blue, green, purple, and orange but a new rule is applied. Each row and each column must contain each color once, and only once. How many coloring possibilities are there?
  7. When you see a map of New Mexico, you will often see each county colored in, but no neighboring county has the same color. What is the minimum number of colors you need to accomplish this:Screen Shot 2019-06-11 at 11.42.05 AM
  8. Same problem as 7, but let’s do this with the continental United States:US