Unsolved graph colouring problems
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].
- Equivalent versions of group-connectivity theorems and conjectures
- Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey
- Vertex colouring and forbidden subgraphs -- a survey
- Polynomials counting nowhere-zero chains in graphs
- Monochromatic subgraphs in randomly colored graphons
- scientific article; zbMATH DE number 4134067 (Why is no real title available?)
- Densities, matchings, and fractional edge-colorings
- scientific article; zbMATH DE number 821271 (Why is no real title available?)
- Chromatic Zagreb and irregularity polynomials of graphs
- Open neighbourhood colouring of some path related graphs
- Modified chromatic Schultz polynomial of some cycle related graphs
- Limit theorems for monochromatic stars
- The Second-Moment Phenomenon for Monochromatic Subgraphs
- A brief history of edge-colorings -- with personal reminiscences
- Frozen development in graph coloring
- Proof of the Goldberg-Seymour conjecture on edge-colorings of multigraphs
- Minimum non-chromatic--choosable graphs
- Some undecidable problems involving the edge-coloring and vertex-coloring of graphs
- Tight bounds on the clique chromatic number
This page was built for publication: Unsolved graph colouring problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2822602)
