Project Links Logo Artwork
Graph Theory: Industrial Drilling
Home > Graph Theory: Industrial Drilling > Solving the Drilling Problem > Modeling it as a Graph Theory Problem
Crib Sheet
Library
Help
Map
Problem List
Module Home
Links Home


conceptsdiscoverapplycollaboratepractice
 
 
go backgo forward
go backgo forward

Modeling it as a Graph Theory Problem

Modeling The Drilling Problem As A Graph Theory Problem

Review

To be sure you are ready to tackle this graph theory problem, take a moment to review the basic definitions.

Make sure, in particular, that you fully understand the definitions of an independent set, a clique, and of vertex coloring.

To check your understanding, prove the following statements:

Problem 26:

A graph is k-chromatic if there is a partitioning of into subsets such that every is an independent set of .

Problem 27:

If is the size of the maximum clique in a graph and is the chromatic number of , then



Equation 12

Problem 28:

If is the size of the maximum independent set in a graph with vertices and chromatic number , then



Equation 13

 
 
go backgo forward
go backgo forward