To get an idea of how extensive is the chromatic theory of graphs, one can open any graph theory book and read the chapters on coloring. To get an idea of how limited is the same theory, one can simply open a particular book, Graph Coloring Problems, a 300-page monograph listing primarily open problems in the subject. Thus we observe a dichotomy: graph coloring enjoys a rich, yet largely incomplete, theory. Since the problems are out there and the foundations are strong, interesting new theorems appear virtually every year.

In this colloquium, I'll introduce some basic graph coloring notions and explore a famous paradoxical theorem of Paul Erdös from 1959. This will set the stage for a natural extension of the chromatic number concept to directed graphs, also known as digraphs. Finally, I'll present a digraph analogue of Erdös' theorem. The proof, discovered in Slovenia last November, uses probabilistic ideas and a surprising application of a fact from basic algebra. Which fact shall remain top secret until the key moment in the talk when it is needed.