ABSTRACT
Using crayons or markers, we can color the vertices of a graph or the edges of a graph (or both, but that’s not done very often). Most of the time, we only care about proper colorings, which for vertices means that no two vertices connected by an edge can be the same color. (And for edges, it means that no two edges that touch a vertex can be the same color. Some of the author’s research is on edge colorings.) Colorings are not just fun but also useful-certain types of information-scheduling problems (e.g., wireless communication) can be solved using graph colorings, as can register allocation issues (in computer science). (Truthfully, graph colorings are only practical when there are few types of constraints on scheduling or allocation problems and when there are no preferences that should be respected. In reality, linear and/or integer programming is used for highly constrained applications. See Bonus Section 7.8 for information on linear and integer programming!)
A coloring of the vertices (or edges) of a graph G is technically a function c : V (G) → C (or c : E(G) → C), where C is a set of colors. But we treat it less formally here, and simply think of a coloring as an assignment of colors to a graph’s vertices (or edges).
