Being Greedy with Crayons
Graph coloring has been studied in various forms for over a century. From
the famous Four Color Theorem, which has implications in map design, to
Dynamic Storage Allocation, which can aid in computer design, graph coloring
has been important partially due to its wide variety of applications. This
talk will focus on the First-Fit algorithm, an online algorithm that views
and colors vertices one at a time, rather than using the structure of the
entire graph to find a proper coloring.
We will consider situations where First-Fit provides good colorings, those
where it fails, and how we determine the difference. Finally, we will discuss
a few applications of online algorithms, specifically scheduling problems and
Dynamic Storage Allocation.