Project Links Logo Artwork
Graph Theory: Industrial Drilling
Home > Graph Theory: Industrial Drilling > Solving the Drilling Problem > First Lower Bound
Crib Sheet
Library
Help
Map
Problem List
Module Home
Links Home


conceptsdiscoverapplycollaboratepractice
 
 
go backgo forward
go backgo forward

First Lower Bound

Finding A Lower Bound

A First Attempt

A fairly obvious way to attempt a coloring proceeds as follows:

  1. First select , the only independent set of size 7, and color its vertices with color1.
  2. Then we can try to find an independent set of size 6 (did you find such a set disjoint from ?) and color those vertices using color2.
  3. We can use the next color, say color3, for the largest independent set composed of vertices that have not yet been assigned a color.

Problem 31:

Continue this way. See how far you can go.

 
 
go backgo forward
go backgo forward