Project Links Logo Artwork
Graph Theory: Industrial Drilling
Home > Graph Theory: Industrial Drilling > Solving the Drilling Problem > A Good Coloring
Crib Sheet
Library
Help
Map
Problem List
Module Home
Links Home


conceptsdiscoverapplycollaboratepractice
 
 
go backgo forward
go backgo forward

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.



 
 
go backgo forward
go backgo forward