NEWS: Steinburg Conjecture is False!

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 Steinburg

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.

Notable Achievements:

  • 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.

Sources: 1 | 2

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


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s