chapter  14
30 Pages

Vertex Colorings

This and the next four chapters will be devoted to perhaps the best known and most studied area of graph theory: graph colorings. In 1993 Noga Alon of Tel Aviv University in Israel, well known for his work in combinatorics and theoretical computer science, wrote:

Graph coloring is arguably the most popular subject in graph theory.