Graphs of large chromatic number

  • Alex Scott

    Mathematical Institute, University of Oxford, Oxford OX2 6GG, United Kingdom
Graphs of large chromatic number cover
Download Chapter PDF

This book chapter is published open access.


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 has small chromatic number then it can be partitioned into a few very simple pieces. But what if 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.