Question

1. (3) Determine the chromatic number of each of the two graphs below. Support your answer by showing a valid coloring, and showing that no fewer colors can be used. 2. (3) Sam has eight friends with whom he wants to have dinner before leaving town for the summer. He has limited time, so he'll try to dine with several at once. His goal is to see all of these friends in as few dinners as possible. Some of these friends don't get along with each other, so he can't have them at the same dinner. The friends to be included are Adam, Ben, Chris, Donna, Ellen, Foster, and Gra- ham. Adam, Ben, and Foster all dislike each other. Chris won't be in the same room with either Ben or Donna. Ellen dislikes Adam, Donna, and Foster. Graham is especially difficult, and only gets along with Ellen. Use a graph model to determine how many separate dinners he'll need to have, being sure to describe what the vertices and edges represent and what object or structure in your model corresponds to a successful dinner plan. 3. (2) Suppose Sam doesn't care whether his friends get along with each other. He decides to have two dinners, and each of the eight friends above will be invited to one of the two. How many different ways could he split up the group of invitations? 4. (2) Sam and the eight friends above decide to go see a movie together. The nine of them all sit in a single row of nine seats. They decide that Adam, Ben, Foster and Graham all have to be separated from each other, and none of them can sit on the aisle. How many different ways could the nine of them line up to accomplish this?

Answer 1

Chromatic Number:

The chromatic number of a graph G is the mininimum number of colours required to colour vertices of the graph properly. It is denoted as X(G)

Properly means no two adjacent vertices share the same colour.

G1 graph contains a complete graph with 5 vertices v₁, v₂, v₃, v₄ and v₅. So we have to colour those vertices with 5 different colours. Thus with less than 5 colors we can not colour the graph properly. Hence chromatic number for graph G₁ is 5.

G₂ graph contains a complete graph with 3 vertices c, h and e. So we have to colour those vertices with 3 different colours. Thus with less than 3 colors we can not colour the graph properly. Hence chromatic number for graph G₂ is 3.

Coloring of the vertices is in the following image.