# Steinberg's conjecture (Solved)

 Importance: Outstanding ✭✭✭✭
 Author(s):
 Subject: Graph Theory » Coloring » » Vertex coloring
 Keywords:
 Posted by: fhavet on: March 7th, 2013
 Solved by: Vincent Cohen-Addad, Michael Hebdige, Daniel Kral, Zhentao Li, Esteban Salgado: Steinberg's Conjecture is false, arXiv:1604.05108

\begin{conjecture} Every planar graph without 4-cycles and 5-cycles is 3-colourable. \end{conjecture}

Borodin et al. [BGRS] who proved that every planar graph without cycles of length in $\{4, \dots ,7\}$ is 3-colourable.

Borodin and Raspaud [BR] proposed the following conjecture which implies Steinberg's Conjecture.

\begin{conjecture}[Strong Bordeaux Conjecture] Every planar graph without 5-cycles and without adjacent triangles is 3-colourable. \end{conjecture}

This conjecture is in turn implied by the following stronger one due to Borodin et al. [BGJR] \begin{conjecture} Every planar graph without 3-cycles adjacent to cycles of length 3 or 5 is 3-colourable. \end{conjecture} Borodin et al. [BGJR06] proved that every planar graph without triangles adjacent to cycles of length from 3 to 9 is 3-colourable.

Steinberg's Conjecture cannot been generalized to list colouring: Voigt [V] constructed a planar graph without 4-cycles and 5-cycles which is not 3-choosable.

% You may use many features of TeX, such as % arbitrary math (between $...$ and $$...$$) % \begin{theorem}...\end{theorem} environment, also works for question, problem, conjecture, ... % % Our special features: % Links to wikipedia: \Def {mathematics} or \Def[coloring]{Graph_coloring} % General web links: \href [The On-Line Encyclopedia of Integer Sequences]{http://www.research.att.com/~njas/sequences/}

## Bibliography

[BGJR] O.V. Borodin, A.N. Glebov, T.R. Jensen, and A.Raspaud. Planar graphs without triangles adjacent to cycles of length from 3 to 9 are 3-colorable. Sib. Elektron. Mat. Izv., 3:428--440, 2006.

[BGRS] O. V. Borodin, A. N. Glebov, A. Raspaud, and M. R. Salavatipour. Planar graphs without cycles of length from 4 to 7 are 3-colorable. J. Combin. Theory Ser. B, 93(2):303--311, 2005.

[BR] O. V. Borodin and A. Raspaud. A sufficient condition for planar graphs to be 3-colorable. J. Combin. Theory Ser. B, 88(1):17--27, 2003.

[V] M. Voigt. \href[A non-3-choosable planar graph without cycles of length 4 and 5]{http://www.sciencedirect.com/science/article/pii/S0012365X06005802}. Discrete Math., 307(7-8):1013--1015, 2007.

% Example: %*[B] Claude Berge, Farbung von Graphen, deren samtliche bzw. deren ungerade Kreise starr sind, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 10 (1961), 114. % %[CRS] Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas: \arxiv[The strong perfect graph theorem]{math.CO/0212070}, % Ann. of Math. (2) 164 (2006), no. 1, 51--229. \MRhref{MR2233847} % % (Put an empty line between individual entries)

* indicates original appearance(s) of problem.

### Steinberg Conjecture disproved

All of the conjectures mentioned here were disproved by Vincent Cohen-Addad, Michael Hebdige, Daniel Kral, Zhentao Li and Esteban Salgado. See https://arxiv.org/abs/1604.05108 .