Answer:
10.8 Graph Coloring
A coloring of a simple graph is the assignment of a color to each vertex of the graph so that no
two adjacent vertices are assigned the same color.
Chromatic number
The chromatic number of a graph is the least number of colors needed for a coloring of this graph.
The Four Color Theorem
The chromatic number of a planar graph is no greater than four.
10.8 pg. 733 # 3
Construct the dual graph for the map shown. Then find the number of colors needed to color the
map so that no two adjacent regions have the same color.
a
b c d e
f
At least three colors are needed to color the
graph because of triangle 4abc exists in the
graph.
10.8 pg. 733 # 7
Find the chromatic number of the given graph.
a
b
c
d
Since this graph forms two triangles, 4abd and
4bcd, we can color this graph with at least 3
colors where a and c are the same colors.
a
b
c
d
10.8 pg. 733 # 9
Find the chromatic number of the given graph.
1
ICS 241: Discrete Mathematics II (Spring 2015)
a
e
b
c
d
This graph can be colored with two colors like
shown.
a
e
b
c
d
10.8 pg. 734 # 19
The mathematics department has six committees, each meeting once a month. How many different
meeting times must be used to ensure that no member is scheduled to attend two meetings at the
same time if the committees are C1 = {Arlinghaus, Brand, Zaslavsky}, C2 = {Brand, Lee, Rosen},
C3 = {Arlinghaus, Rosen, Zaslavsky}, C4 = {Lee, Rosen, Zaslavsky}, C5 = {Arlinghaus, Brand},
and C6 = {Brand, Rosen, Zaslavsky}?
We will first draw the intersection graph of the given sets.
C1 C2
C3
C5 C4
C6
From here, it is easy to see that we need at least 5 colors like so:
C1 C2
C3
C5 C4
C6
Therefore, 5 meeting times are needed. Committees C4 and C5 can meet at the same time.
Step-by-step explanation:
done-_-