You're reading: News, Phil. Trans. Aperiodic.

Steinberg’s conjecture is false

Conjecture   Every planar graph without 4-cycles and 5-cycles is 3-colourable.

Nope!

In a paper just uploaded to the arXivVincent 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

Leave a Reply

  • (will not be published)

$\LaTeX$: You can use LaTeX in your comments. e.g. $ e^{\pi i} $ for inline maths; \[ e^{\pi i} \] for display-mode (on its own line) maths.

XHTML: You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>