Table of Contents
 
Slides
Hour 1
The first hour will cover a general overview of graph coloring. Topics that will be discussed include a series of applications that fit the domain of graph coloring (such as trying to color a planar map and scheduling problems), definitions and terminology that is associated with graph coloring (such as the chromatic number and the k-coloring of a graph) and existing results of graph coloring. Some examples of existing results which will be looked at include:
  • A Complete graph of n vertices, Kn, requires at least n colors.
  • The chromatic number of a cycle of length n, Cn, is 2 if the cycle is even.
  • A complete Bipartite graph with m sets of vertices and n sets of vertices can be colored using at most two colors.
Examples of both edge and vertex colored graphs will also be given.

Hour 2
During the remainder of the first class there will be a quick introduction to Bipartite and Planar Graphs. This will include an algorithm for determining if a given graph is two colorable (this algorithm was already seen in Algorithms since determining if a graph is bipartite is necessary and sufficient for showing a graph to be 2-colorable). The notion of 4-colorability of planar graphs will also be investigated. I will include a history of the problem along with the stumbling blocks that have been encountered along the way. The end of this discussion will include looking at the use of computers in proving the result.

Hours 3 and 4
This talk will introduce two problems that have been investigated in graph coloring. The first problem that will be investigated will be to determine if graph is 3-colorable. The second problem will be to find a minimum coloring of a graph. Two different approaches will be discussed to solving this problem. The first is a contraction algorithm called the Recursive-Largest-First (RLF). The second is a sequential coloring algorithm called the Largest First (LF) algorithm. In each case pseudo-code, and example and timings will be discussed. It is known that these problems are NP-complete. For example, problem 2 can be shown to be NP-complete by reducing the 3-satisfiability problem (3-SAT) to Colorability. I would also like to find a good algorithm for edge colorings. When I find such an algorithm that I find interesting I will be looking to add it to the talk as well.

Time Permitting
If there is time that remains a number of other areas can be discussed including plane-coloring, the coloring of hypergraphs and non-deterministic methods of approximation.