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.) ACTIVITY 2 Answer the following questions:
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.
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.
ACTIVITY 4 Turn the 2 maps below into graphs.
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.
Additional Exercises 1. Draw a graph to represent this map.
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.
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!
