The Inside View
The "Inside View"
How far did you get?
You probably found this approach to be quite difficult.
Let's try the problem from the other "end", and see if we
have more success.
Let's look at the points in the
middle of the figure. It is clear
that these points are "close" to one another, and therefore
form a clique. The size of this clique is a lower bound for
the chromatic number.
Let us try to find as large a clique as possible.
Figure 28: The Largest Clique
The 24 vertices inside the yellow-shaded area comprise
a clique. This is the largest clique of the graph.
Corollary: Any drilling tool that
satisfies the given constraints must use at least 24
passes.
|
Thus, 24 is our new lower bound!
|
|