Vertex colouring and forbidden subgraphs -- a survey (Q1889838)

The monograph ``Graph coloring problems'' by \textit{T. R. Jensen} and \textit{B. Toft} (Wiley, New York) (1995; Zbl 0855.05054) provides a comprehensive list of unsolved problems in chromatic graph theory. The present survey gives an account of the recent development in the area. It focusses in the recent solution of Berge's strong perfect graph conjecture proved by Chudnovsky, Robertson, Seymour and Thomas, and some related unsolved problems. Then the authors consider the more general problem of finding an upper bound for the chromatic number as a function of the clique number. One such problem is the conjecture of B. Reed that the chromatic number is always bounded above by \((\omega+ \Delta)/2\) where \(\omega\) is the clique number, and \(\Delta\) is the maximum degree. The authors also discuss upper bounds on the chromatic number in graphs where specific subgraphs are excluded. The survey contains many unsolved problems and references.