Graph Theory: Industrial Drilling
Home
>
Graph Theory: Industrial Drilling
> Solving the Drilling Problem > Vertex Coloring
Crib Sheet
Library
Help
Map
Problem List
Module Home
Links Home
The Drilling Problem
Objectives
Foundations
What is a Graph?
Edges and Vertices
A First Theorem
Types of Graphs
Subgraphs and Supergraphs
Walks, Paths, Cycles
Trees
Solving the Drilling Problem
Independent Sets, Cliques, etc.
Vertex Coloring
Modeling it as a Graph Theory Problem
First Lower Bound
The Inside View
A Good Coloring
The Best Coloring
What's Next?
concepts
discover
apply
collaborate
practice
Vertex Coloring
Problem 25:
What is the chromatic number of the following graph?
Figure 24:
Answer
Copyright 1999 Rensselaer Polytechnic Institute. All Rights Reserved.