A Good Coloring
The solution below uses 25 colors.
... which is only one above our just-established lower bound of
.
Our coloring uses three groups of color classes.
Each of these groups of color classes corresponds to a
different configuration of drill bits on the gang drill.
Figure 29:
The first group consists of just one color class.
You will recognize if as the independent set with 7 vertices;
the largest independent set in the graph.
Figure 30:
The second group has 12 color classes, each of size 4.
A class from this group - four yellow vertices - is shown on the right.
Figure 31:
Every other class in the second group is obtained from this class by moving it either right
and/or down.
The yellow vertices in the figure on the left comprise the union of these color classes.
Figure 32:
The third group of color classes is represented by an independent set comprised
of 3 green vertices in the figure to the right.
There are 12 classes in the third group, each of size 3.
Figure 33:
Similarly to the second group, every class from the third group is obtained from the
green class by moving it down and/or to the right.
|