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


conceptsdiscoverapplycollaboratepractice
 
 
go backgo forward
go backgo forward

The Best Coloring

25 is the right answer!



Figure 34:

Consider the 31 points in the middle of the figure on the right. of them are shown as yellow diamonds; the remainder are shown as red stars.



Proposition 1:

The distance between any two diamonds is less than 35.

Proposition 2:

The distance between any diamond and any star is less than 35.

Corollaries:

  1. For any coloring of , the 19 diamonds use 19 distinct colors.
  2. For any coloring of , the 19 diamonds use colors different from those used for the stars.
  3. If is the number of colors needed to color the 12 stars, the number of colors needed for coloring is at least



Equation 15



Figure 35:

The three green stars are the only points at a distance greater than 35 from the red star. Hence, only these points can be colored the same color as the red star. The distance between any two of the green stars is less than 35, however. Thus any coloring of the twelve diamonds uses any color at most twice, implying that



Therefore, the chromatic number of is 25.

We now know that the coloring just given is indeed a best coloring.

Using this scheme, we can drill the workpiece in only 25 passes. Furthermore, we need only 3 different configurations of the gang drill's bits, corresponding to each of the groups of color classes.

 
 
go backgo forward
go backgo forward