Conjecture Every planar graph without 4-cycles and 5-cycles is 3-colourable.
Nope!
In a paper just uploaded to the arXiv, Vincent Cohen-Addad, Michael Hebdige, Daniel Kral, Zhentao Li and Esteban Salgado show the construction of a graph with no cycles of length 4 or 5 which isn’t 3-colourable: it isn’t possible to assign colours to its vertices so that no pair of adjacent vertices have the same colour, using only three different colours. This is a counterexample to a conjecture of Richard Steinberg from 1976.
The problem was listed in the Open Problem Garden as of “outstanding” importance.
Read the paper: Steinberg’s conjecture is false
via Parcly Taxel on Twitter
