← All problems

Strong Bordeaux Conjecture on 3-coloring planar graphs

16 years old · traced to

Let GG be a planar graph. Strong Bordeaux Conjecture. If no pair of cycles of length three in GG shares an edge and GG has no cycle of length five, then GG is 3-colorable. This conjecture is explicitly stated to be disproved by the same counterexample that disproves Steinberg's conjecture.

References

3 papers in this index state this conjecture (2010–2016). The statement above is taken from the most recent of them; the others are arXiv:1508.07890, arXiv:1004.0582.

Status

  • Refuted: Vincent Cohen-Addad, Michael Hebdige, Daniel Král’, Zhentao Li, and Esteban Salgado. Steinberg’s Conjecture is false (arXiv, 2016) https://arxiv.org/abs/1604.05108

Source: Vincent Cohen-Addad, Michael Hebdige, Daniel Kral, Zhentao Li and Esteban Salgado, “Steinberg's Conjecture is false”, arXiv:1604.05108 (2016).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.