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

At this point, we can already establish some kind of lower bound for the number of colors needed:

Every coloring of the graph G must use at least 13 colors.

Proof

Since the size of every independent set is at most 7, the number of colors used by any coloring must be at least



Equation 14

 
 
go backgo forward
go backgo forward