Steinberg's conjecture is false
From MaRDI portal
Publication:345097
DOI10.1016/J.JCTB.2016.07.006zbMATH Open1350.05018arXiv1604.05108OpenAlexW2963985217WikidataQ105319014 ScholiaQ105319014MaRDI QIDQ345097FDOQ345097
Authors: Vincent Cohen-Addad, Michael Hebdige, Daniel Král', Zhentao Li, Esteban Salgado 
Publication date: 25 November 2016
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Abstract: Steinberg conjectured in 1976 that every planar graph with no cycles of length four or five is 3-colorable. We disprove this conjecture.
Full work available at URL: https://arxiv.org/abs/1604.05108
Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)
Cites Work
- Colorings of plane graphs: a survey
- Title not available (Why is that?)
- Planar graphs without 5- and 7-cycles and without adjacent triangles are 3-colorable
- Title not available (Why is that?)
- On 3-colorable plane graphs without 5- and 7-cycles
- A sufficient condition for planar graphs to be 3-colorable
- Planar graphs without cycles of length from 4 to 7 are 3-colorable
- A note on the three color problem
- Planar graphs without triangles adjacent to cycles of length from 3 to 9 are 3-colorable
- Title not available (Why is that?)
- Structural properties of plane graphs without adjacent triangles and an application to 3-colorings
- Planar graphs without triangles adjacent to cycles of length from 4 to 7 are 3-colorable
- A non-3-choosable planar graph without cycles of length 4 and 5
Cited In (52)
- Title not available (Why is that?)
- Planar graphs having no cycle of length 4, 7, or 9 are DP-3-colorable
- Gaps in the cycle spectrum of 3-connected cubic planar graphs
- Every planar graph without adjacent cycles of length at most 8 is 3-choosable
- Flexibility of planar graphs -- sharpening the tools to get lists of size four
- Backbone coloring of graphs with galaxy backbones
- The \((3, 3)\)-colorability of planar graphs without 4-cycles and 5-cycles
- Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8
- 1-planar graphs with girth at least 6 are (1,1,1,1)-colorable
- Further extensions of the Grötzsch theorem
- Square Coloring Planar Graphs with Automatic Discharging
- Partitioning planar graphs without 4-cycles and 6-cycles into a linear forest and a forest
- 4-choosability of planar graphs with 4-cycles far apart via the Combinatorial Nullstellensatz
- Plane Graphs without 4- and 5-Cycles and without Ext-Triangular 7-Cycles are 3-Colorable
- Title not available (Why is that?)
- Circular backbone colorings: on matching and tree backbones of planar graphs
- Partitioning planar graphs without 4-cycles and 5-cycles into bounded degree forests
- Planar graphs without 4-cycles and close triangles are \((2,0,0)\)-colorable
- Defective 2-colorings of planar graphs without 4-cycles and 5-cycles
- The Strong Fractional Choice Number and the Strong Fractional Paint Number of Graphs
- Planar graphs without 5-cycles and intersecting triangles are \((1, 1, 0)\)-colorable
- Every planar graph without 5-cycles and \(K_4^-\) and adjacent 4-cycles is \((2, 0, 0)\)-colorable
- Note on 3-choosability of planar graphs with maximum degree 4
- Planar graphs without adjacent cycles of length at most five are \((1,1,0)\)-colorable
- A Steinberg-like approach to describing faces in 3-polytopes
- Characterization of Cycle Obstruction Sets for Improper Coloring Planar Graphs
- Circular coloring and fractional coloring in planar graphs
- Fractional coloring planar graphs under Steinberg-type conditions
- Choosability with union separation of planar graphs without cycles of length 4
- Planar graphs without 4- and 6-cycles are (7 : 2)-colorable
- The Gotsman-Linial Conjecture is False
- Mapping sparse signed graphs to (K2k,M) $({K}_{2k},M)$
- A note on the three color problem on planar graphs without 4- and 5-cycles and without ext-triangular 7-cycles
- Every planar graph without 4-cycles and 5-cycles is (3,3)-colorable
- Steinberg-like theorems for backbone colouring
- Every planar graph without triangles adjacent to cycles of length 3 or 6 is \(( 1 , 1 , 1 )\)-colorable
- A refinement of choosability of graphs
- 3-Paintability of planar graphs
- Planar graphs without 3-cycles adjacent to cycles of length 3 or 5 are \((3, 1)\)-colorable
- Decomposing a planar graph without triangular 4-cycles into a matching and a 3-colorable graph
- Every signed planar graph without cycles of length from 4 to 8 is 3-colorable
- Note on improper coloring of $1$-planar graphs
- New restrictions on defective coloring with applications to Steinberg-type graphs
- A relaxation of Novosibirsk 3-color conjecture
- Every planar graph without 3-cycles adjacent to 4-cycles and without 6-cycles is (1, 1, 0)-colorable
- \((1,0,0)\)-colorability of planar graphs without cycles of length \(4\) or \(6\)
- Planar graphs without adjacent cycles of length at most five are (2, 0, 0)-colorable
- An introduction to the discharging method via graph coloring
- Every planar graph without cycles of length 4 or 9 is \((1, 1, 0)\)-colorable
- Planar graphs without cycles of length 4 or 5 are \((11 : 3)\)-colorable
- Title not available (Why is that?)
- Hyperbolic families and coloring graphs on surfaces
This page was built for publication: Steinberg's conjecture is false
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q345097)
