The Steinburg conjecture, proposed by Richard Steinberg in 1976, is a problem in Graph Theory which states that:
“Every planar graph without 4-cycles and 5-cycles is 3-colourable.”
The property of a graph being 3-colourable means that it is possible to assign colours to its vertices so that no pair of adjacent vertices have the same colour, using only three different colours.
Robert Steinberg was born in 1922 and was a mathematician at UCLA. He made many important contributions to mathematics, including the Steinberg representation, the Lang-Steinberg theorem, the Steinberg group in algebraic K-theory and Steinberg’s formula in representation theory.
- 1966: he was an invited speaker at the International Congress of Mathematics;
- 1985: won a Steele Prize, which is presented for distinguished research work and writing in mathematics;
- 1985: he was elected to the National Academy of Sciences;
- 1990: won the Jeffery-Williams Prize.
“I have had a good life.” – Robert Steinberg
A paper, recently uploaded to the arXiv, by Vincent Cohn-Addad, Michael Hebdige, Daniel Kral, Zhentao Li and Esteban Salgado, shows the construction of a graph with no cycles of length 4 or 5 that isn’t 3 colourable. This is a direct counterexample to the conjecture, hence proving it to be false.
I had another post planned for today but I recently read this news and decided to make a post about it! Hope you enjoy. M x