ACTIVITY 1: Print out this map (or copy it into a graphics program) and color the map of the continental U.S. using the minimum number of colors. Numbers may be used to represent colors if you don’t have colors.

RULE: No 2 states sharing a common border may be the same color. States whose boundaries only meet at a point may be the same color.

Try one of these related links. (One produces a smaller map, the other a larger map.)
Smaller map version
Larger map version

ACTIVITY 2

Answer the following questions:

• What is the goal of a map coloring problem?
• What assumption are we making about the regions that make up the map to be colored?
• Define Chromatic Number.
• State Brook's Theorem.

Print out (or copy into a Paint program) and color each of the maps below. Numbers may be used to represent colors if you don’t have colors.
Also, determine the chromatic number of each map.

ACTIVITY 3

Use Brook’s Theorem to find a maximum for the chromatic number of the graph below.

How many colors are actually needed to color this graph?

Color the map shown below. Find the chromatic number of the graph.

The graph above is basically just a pie chart.

• Experiment with other pie charts having varying numbers of sectors. Show your work.
• Use your results to predict the chromatic number for pie charts with a) 37 sectors b) 52 sectors
• What can you say, in general, about coloring pie charts?

ACTIVITY 4

Turn the 2 maps below into graphs.

• Use vertex coloring on the graphs above to find the chromatic number of each graph.
• Verify that the vertex coloring scheme actually works by coloring each of the original maps using the coloring scheme from the map’s associated graph.

ACTIVITY 5

The graph below comes from a video from class.

Use vertex coloring to assign the animals to the minimum number of areas. List your final groupings.

(Remember that an edge between two animals means that the two animals cannot be housed together.)

ACTIVITY 6

Suppose a pet store has 10 types of fish. Some of the species naturally are prone to attack each other and therefore cannot be stored in the same tank. In the chart below, an X shows which species are incompatible with each other.

• Draw a graph that represents the information in this table.

• What is the maximum number of tanks needed as guaranteed by Brook’s Theorem?

• What is the minimum number of tanks actually needed to keep the fish?

• Label the tanks A, B, C, etc. and show your solution.

Additional Exercises

1. Draw a graph to represent this map.

• What is the chromatic number?

• Color the above map with the minimum number of colors.

2. Color the vertices of these graphs using the minimum number of colors. Make up a map based on each of the graphs above and color each using the minimum number of colors.

3. The graph below shows the courses that students take during a summer session at a small college. The vertices represent courses and an edge between two vertices indicates that the courses represented by the two vertices have at least one student that is enrolled in both courses.

Find the minimum number of time slots needed to schedule final exams for these courses so that no student is scheduled to take two or more exams at the same time. SHOW YOUR WORK!

3. Use Brook’s Theorem to find a maximum for the chromatic number of the graph below.

How many colors are actually needed to color this graph?

4. Politically Correct High School offers several clubs for their students. Some students are officers in more than one club. There will be a single activity period on certain days during which clubs must meet. Since officers must attend meetings, you must decide on which days the clubs will meet so that clubs that share officers will not meet on the same day. The chart below gives the pertinent information. An X indicates that two clubs share officers.

• Draw a graph that represents this information. Label the vertices!
• What does Brook’s Theorem say about this problem?
• What is the minimum number of days that must be used for club meetings so that no officer will be forced to miss a meeting?
• Describe a workable schedule which lists each club and its meeting day.

5. A scoutmaster is organizing a trip to a nearby lake. From past experience, he knows that certain boys will cause problems if they are together in the same car during the trip. If a car can hold no more than 5 boys, how many cars will be needed to transport the boys? The relevant information in shown in the table below. An X indicates that the boys must not travel together in the same car. SHOW ALL YOUR WORK!