Unsolved graph colouring problems (Q2822602)

Graph colouring problems continue to remain at the heart of the entire body of graph theory even after more than twenty years of publication of the book [Graph colouring problems. New York, NY: Wiley (1995; Zbl 0855.05054)] by the authors. The article under review is a very interesting and comprehensive account of important unsolved problems on graph colourings and includes a survey of some very carefully chosen difficult and significant questions in this area. Few details are included in the present review to entice a reader to read the full article. The first introductory section lists seven most striking results on graph colourings that have been obtained after the publication of the book mentioned in a previous sentence. \textit{H. Hadwiger} [Vierteljahresschr. Naturforsch. Ges. Zürich 88, 133--142 (1943; Zbl 0061.41308)] conjectured that every \(n\)-chromatic graph can be transformed into \(K_n\), the complete graph on \(n\) vertices through a sequence of contraction of edges and deletion of edges and vertices of such a graph. Section 2 of the article discusses some important development on this problem as also on the Erdős-Faber-Lovász conjecture which states that if a graph \(G\) is constructed by taking \(n\) copies of \(K_n\) with any two copies having at the most one vertex in common, then \(G\) has chromatic number \(n\). The third section deals with graphs on surfaces at a considerable length that is well deserved. Section 4 deals with degrees and colourings along with the inclusion of new ideas on probability colourings. Section 5 on edge colourings gives a very nice account of the Berge-Fulkerson conjecture and the list colouring problem. Section 6 is devoted to flow problems and includes discussion on the flow conjectures of Tutte. The article is very well written and is a must for anyone who is even superficially interested in studying any problem connected with graph colouring.NEWLINENEWLINEFor the entire collection see [Zbl 1317.05004].