CS 163/265--Graph Algorithms Homework 7
Due: Friday, June 2, 11:45pm
Please answer the following questions, each of which is worth 10 points.
1. (CS 163 students only) Show that the Gr¨otzsch graph (see link below) can be (vertex) colored using 4 colors. https://en.wikipedia.org/wiki/Gr%C3%B6tzsch_graph
2. (CS 265 students only) Show that the Gr¨otzsch graph (see link above) cannot be (vertex) colored using 3 colors.
3. Prove that the chromatic number of a disconnected graph is the largest chromatic number of any of its connected components.
4. What is the chromatic number of a graph obtained from Kn by removing one edge, where n ≥ 3? https://en.wikipedia.org/wiki/Complete_graph 5. The following committees need to have meetings scheduled: A={Smith, Jones, Brown, Green} B={Jones, Wagner, Chase} C={Harris, Oliver} D={Harris, Jones, Mason} E={Oliver, Cummings, Larson} Are three meeting times (using multiple rooms) sufficient to schedule the committees so that no member has to be at two meetings simultaneously? Justify your answer. (Hint: explain how to model this problem using a graph.)
6. The following tours of garbage trucks in Orange County are being considered by the Orange County waste management company. Tour 1: The Spectrum, Diamond Jamboree, and the Great Park Tour 2: The Bluffs, the Great Park, the Spectrum Tour 3: Segerstrom Center, Hoag Hospital, and UCI Tour 4: University Center and the Great Park Tour 5: University Center, Disneyland, and the Spectrum Tour 6: Segerstrom Center, Angels Stadium, and Hoag Hospital Tour 7: Disneyland, Crystal Cove Beach, and Hoag Hospital
Assuming the sanitation workers refuse to work more than three days a week, can these tours be partitioned so that no site is visited more than once on a given day? Justify your answer. (Hint: explain how to model this problem using a graph.)