Scribd
Upload
5K views10 pages

MMW Exercise Set 6.4

This document contains solutions to graph coloring exercises. It discusses coloring maps and graphs using the fewest number of colors such that no adjacent regions/vertices share a color. It also discusses determining the chromatic number of graphs through trial and error and designing schedules by coloring graphs representing incompatibility between items. The document provides reasoning and solutions for various graph coloring problems.

Uploaded by

Cpa
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
5K views10 pages

MMW Exercise Set 6.4

This document contains solutions to graph coloring exercises. It discusses coloring maps and graphs using the fewest number of colors such that no adjacent regions/vertices share a color. It also discusses determining the chromatic number of graphs through trial and error and designing schedules by coloring graphs representing incompatibility between items. The document provides reasoning and solutions for various graph coloring problems.

Uploaded by

Cpa
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 10

CUETO, GRACEANNE D.

BSA-1103

CHAPTER 6
EXERCISE SET 6.4
 Map Coloring In Exercises 1 to 4, a fictional map of the countries of a continent is given.
Represent the map by a graph and find a coloring of the graph that uses the fewest possible
number of colors. Then color the map according to the graph coloring you found.

2.

Answer:

4 colors are needed to color the graph.

4.
CUETO, GRACEANNE D.
BSA-1103

Answer:

4 colors are needed to color the graph.

 Map Coloring In Exercises 5 to 8, represent the map by a graph and find a coloring of the
graph that uses the smallest possible number of colors.

6. Counties of New Hampshire

Answer:
CUETO, GRACEANNE D.
BSA-1103

3 is the smallest possible number of colors needed to color the graph.

8. Provinces of South Africa

Answer:

3 colors are needed to color the graph.


CUETO, GRACEANNE D.
BSA-1103

 In Exercises 9 to 14, show that the graph is 2-color by finding a 2-coloring. If the graph is not 2-
colorable explain why.

10.

Circuit B-E-D-C-E-F-D-B consists of 7 vertices. According to 2 colorable theorem a graph


is 2-colorable if and only if it has no circuits that consist of an odd number of vertices.
Therefore, the given graph is not 2 colorable.

12.

None of the possible circuit in the given graph have odd number of vertices therefore it
is a 2-colorable graph.

14.
CUETO, GRACEANNE D.
BSA-1103

In the given graph none of the possible circuits have odd number of vertices therefore it
is 2-colorable graph.

 In Exercises 15 to 20, determine (by trial and error) the chromatic number of the graph.

16.

By trial and error, we can find a 4-coloring graph. Thus, the chromatic number of the
graph is 4.

18.

By trial and error, we can find a 3-coloring graph. Thus, the chromatic number of the
graph is 3.

20.
CUETO, GRACEANNE D.
BSA-1103

By trial and error, we can find a 5-coloring graph. Thus, the chromatic number of the
graph is 5.

22. Scheduling Eight political committees must meet on the same day, but some members are
on more than one committee. Thus any committees that have members in common cannot meet
at the same time. An “X” in the following table indicates that the two corresponding committees
share a member. Use graph coloring to determine the minimum number of meeting times that will
be necessary so that all members can attend the appropriate meetings.

Appropriations Budget Finance Judiciary Education Health Foreign Affairs Housing


Appropriations - X X X
Budget - X X
Finance X - X X X
Judiciary X X - X X
Education - X X
Health X X X -
Foreign Affairs X X X -
Housing X X X -

3 meeting times are necessary so that all members can attend the appropriate meetings.
24. Scheduling Five different charity organizations send trucks on various routes to pick up
donations that residents leave on their doorsteps.
CUETO, GRACEANNE D.
BSA-1103

Charity A covers Main St., First Ave., and State St.


Charity B covers First Ave., Second Ave., and Third Ave.
Charity C covers State St., City Dr., and Country Lane.
Charity D covers City Dr., Second Ave., and Main St.
Charity E covers Third Ave., Country Lane, and Fourth Ave.
Each charity has its truck travel down all three streets on its route on the same day, but no two
charities wish to visit the same streets on the same day. Use graph coloring to design a schedule
for the charities. Arrange their pickup routes so that no street is visited twice on the same day by
different charities. The schedule should use the smallest possible number of days.

The schedule should use at least 3 days.


26. Animal Housing A researcher has discovered six new species of insects overseas and
needs to transport them home. Some species will harm each other and so cannot be transported
in the same container.
Species A cannot be housed with species C or F.
Species B cannot be housed with species D or F.
Species C cannot be housed with species A, D, or E.
Species D cannot be housed with species B, C, or F.
Species E cannot be housed with species C or F.
Species F cannot be housed with species A, B, D, or E.
Draw a graph where each vertex represents a species of insect and an edge connects two vertices
if the species cannot be housed together. Then use graph coloring to determine the minimum
number of containers the researcher will need to transport the insects.
CUETO, GRACEANNE D.
BSA-1103

Answer:

The researcher will need 3 containers to transport the insects.


28. Map Coloring Draw a map of a fictional continent consisting of four countries, where the
map cannot be colored with three or fewer colors without adjacent countries sharing a color.
Answer:

In the graph one country is connected to all the other countries of the continent and no
other connected edge is present in the graph.
30. Edge Coloring In this section, we colored vertices of graphs so that no edge connected two
vertices of the same color. We can also consider coloring edges, rather than vertices, so that no
vertex connects two or more edges of the same color. In parts a to d, assign each edge in the
graph a color so that no vertex connects two or more edges of the same color. Use the fewest
number of colors possible.
CUETO, GRACEANNE D.
BSA-1103

Answer:

a.

b.
CUETO, GRACEANNE D.
BSA-1103

c.

d.

The number of colors required will always be at least the number of edges that meet
at the vertex of highest degree in the graph because no vertex connects two or more
edges of the same color.

You might also like