Graphs of large chromatic number

Abstract

The chromatic number has been a fundamental topic of study in graph theory for more than 150 years. Graph coloring has a deep combinatorial theory and, as with many NP-hard problems, is of interest in both mathematics and computer science. An important challenge is to understand graphs with very large chromatic number. The chromatic number tells us something global about the structure of a graph: if $G$ has small chromatic number then it can be partitioned into a few very simple pieces. But what if $G$ has large chromatic number? Is there anything that we can say about its local structure? In particular, are there particular substructures that it must contain? In this paper, we will discuss recent progress and open problems in this area.