Question

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,

\(\begin{array}{*{20}{l}}\begin{array}{l}{C_1} = \{ \;Arlinghaus, Brand, Zaslavsky\;\} ,\\{C_2} = \{ \;Brand, Lee, Rosen\;\} ,\end{array}\\\begin{array}{l}{C_3} = \{ \;Arlinghaus, Rosen, Zaslavsky\;\} ,\\{C_4} = \{ \;Lee, Rosen, Zaslavsky\;\} ,\end{array}\\\begin{array}{l}{C_5} = \{ \;Arlinghaus, Brand\;\} ,\\{C_6} = \{ \;Brand, Rosen, Zaslavsky\;\} \end{array}\end{array}\)

Short answer

The number of different meeting times is \(5\) .

Step-by-step solution

The given information

Given that,

Number of committees=\(6\)

\(\begin{array}{*{20}{l}}\begin{array}{l}{C_1} = \{ {\rm{\;Arlinghaus, Brand, Zaslavsky\;}}\} ,\\{C_2} = \{ {\rm{\;Brand, Lee, Rosen\;}}\} ,\end{array}\\\begin{array}{l}{C_3} = \{ {\rm{\;Arlinghaus, Rosen, Zaslavsky\;}}\} ,\\{C_4} = \{ {\rm{\;Lee, Rosen, Zaslavsky\;}}\} ,\end{array}\\\begin{array}{l}{C_5} = \{ {\rm{\;Arlinghaus, Brand\;}}\} ,\\{C_6} = \{ {\rm{\;Brand, Rosen, Zaslavsky\;}}\} \end{array}\end{array}\)

Definition of chromatic number of graph

It is the minimal number of colors needed to color the vertices in such a way that no two adjacent vertices have the same color.

Step 3:Calculation required

Let the numbers in the committees are:

Arlinghaus=\(1\)

Brand=\(2\)

Zaslavsky=\(3\)

Lee=\(4\)

Rosen=\(5\)

\(\begin{array}{*{20}{l}}\begin{array}{l}{C_1} = \{ 1,2,3\} ,\\{C_2} = \{ 2,4, \supset \} \end{array}\\\begin{array}{l}{C_3} = \{ 1,5,3\} ,\\{C_4} = \{ 4,5,3\} \end{array}\\\begin{array}{l}{C_5} = \{ 1,2\} ,\\{C_6} = \{ 2,5,3\} \end{array}\end{array}\)

In the conflict graph \(G\) , where,

\(V(G) = \left\{ {{C_1},{C_2},{C_3},{C_4},{C_5},{C_6}} \right\}\),

\({S_i},{S_j} \in E(G){\rm{\;iff\;}}{S_i} \cap {S_j} \ne \phi \)

The vertex is,

\(\begin{array}{l}{C_5} \cap {C_4} = \{ 1,2\} \cap \{ 4,5,3\} \\ = \phi \end{array}\)

Hence, the chromatic number of the graph \(G\)is \(5\).