Abstract: Steinberg conjectured in 1976 that every planar graph with no cycles of length four or five is 3-colorable. We disprove this conjecture.
Cites work
- A non-3-choosable planar graph without cycles of length 4 and 5
- A note on the three color problem
- A sufficient condition for planar graphs to be 3-colorable
- Colorings of plane graphs: a survey
- scientific article; zbMATH DE number 434910 (Why is no real title available?)
- scientific article; zbMATH DE number 54790 (Why is no real title available?)
- scientific article; zbMATH DE number 821271 (Why is no real title available?)
- On 3-colorable plane graphs without 5- and 7-cycles
- Planar graphs without 5- and 7-cycles and without adjacent triangles are 3-colorable
- Planar graphs without cycles of length from 4 to 7 are 3-colorable
- Planar graphs without triangles adjacent to cycles of length from 3 to 9 are 3-colorable
- Planar graphs without triangles adjacent to cycles of length from 4 to 7 are 3-colorable
- Structural properties of plane graphs without adjacent triangles and an application to 3-colorings
Cited in
(62)- Circular backbone colorings: on matching and tree backbones of planar graphs
- Defective 2-colorings of planar graphs without 4-cycles and 5-cycles
- Every signed planar graph without cycles of length from 4 to 8 is 3-colorable
- Planar graphs without 3-cycles adjacent to cycles of length 3 or 5 are \((3, 1)\)-colorable
- Every planar graph without 3-cycles adjacent to 4-cycles and without 6-cycles is (1, 1, 0)-colorable
- Planar graphs without adjacent cycles of length at most five are (2, 0, 0)-colorable
- \((1,0,0)\)-colorability of planar graphs without cycles of length \(4\) or \(6\)
- A relaxation of Novosibirsk 3-color conjecture
- A note on the three color problem on planar graphs without 4- and 5-cycles and without ext-triangular 7-cycles
- Partitioning planar graphs without 4-cycles and 6-cycles into a linear forest and a forest
- Further extensions of the Grötzsch theorem
- Every planar graph without triangles adjacent to cycles of length 3 or 6 is \(( 1 , 1 , 1 )\)-colorable
- Planar graphs without 4- and 6-cycles are (7 : 2)-colorable
- New restrictions on defective coloring with applications to Steinberg-type graphs
- Partitioning planar graphs without 4-cycles and 5-cycles into bounded degree forests
- Gaps in the cycle spectrum of 3-connected cubic planar graphs
- Flexibility of planar graphs -- sharpening the tools to get lists of size four
- Decomposing a planar graph without triangular 4-cycles into a matching and a 3-colorable graph
- Every planar graph without 5-cycles and \(K_4^-\) and adjacent 4-cycles is \((2, 0, 0)\)-colorable
- A refinement of choosability of graphs
- Every planar graph without adjacent cycles of length at most 8 is 3-choosable
- Planar graphs without cycles of length 4 or 5 are (11 : 3)-colorable
- Note on 3-choosability of planar graphs with maximum degree 4
- Every planar graph without cycles of length 4 or 9 is \((1, 1, 0)\)-colorable
- A Steinberg-like approach to describing faces in 3-polytopes
- Choosability with union separation of planar graphs without cycles of length 4
- 4-choosability of planar graphs with 4-cycles far apart via the Combinatorial Nullstellensatz
- The \((3, 3)\)-colorability of planar graphs without 4-cycles and 5-cycles
- scientific article; zbMATH DE number 5666686 (Why is no real title available?)
- 3-paintability of planar graphs
- Hyperbolic families and coloring graphs on surfaces
- Characterization of Cycle Obstruction Sets for Improper Coloring Planar Graphs
- The Gotsman-Linial Conjecture is False
- The Strong Fractional Choice Number and the Strong Fractional Paint Number of Graphs
- An introduction to the discharging method via graph coloring
- Note on improper coloring of 1-planar graphs.
- Plane graphs without 4- and 5-cycles and without ext-triangular 7-cycles are 3-colorable
- Steinberg-like theorems for backbone colouring
- Backbone coloring of graphs with galaxy backbones
- Circular coloring and fractional coloring in planar graphs
- Three coloring via triangle counting
- Mapping sparse signed graphs to (K2k,M) $({K}_{2k},M)$
- Every planar graph without 4-cycles and 5-cycles is (3,3)-colorable
- Fractional coloring planar graphs under Steinberg-type conditions
- 1-planar graphs with girth at least 6 are (1,1,1,1)-colorable
- Square Coloring Planar Graphs with Automatic Discharging
- The surviving rate of planar graphs without short cycles
- Planar graphs having no cycle of length 4, 7, or 9 are DP-3-colorable
- Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8
- Planar graphs without cycles of length 4 or 5 are (7 : 2)-colorable
- Flexibility of planar graphs without C₄ and C₅
- On the strong Bordeaux conjecture
- \((\mathcal{F}_1, \mathcal{F})\)-partition of plane graphs without 4- and 5-cycles and without ext-triangular 7-cycles
- Vertex partitions of \((C_4,C_5,C_{10})\)-free planar graphs
- An \((\mathcal{F}_2, \mathcal{F}_6)\)-partition of planar graphs without cycles of length 4 and 6
- An \((\mathcal{F}_3, \mathcal{F}_4)\)-partition of planar graphs without 4- and 6-cycles
- (I,F)-partition of planar graphs without cycles of length 4, 6, or 9
- Planar graphs with no incident triangles and no 4- or 5-cycles are (7:2)-colorable
- Planar graphs without 4-cycles and close triangles are \((2,0,0)\)-colorable
- The independence ratio of 4-cycle-free planar graphs
- On a 3-coloring of plane graphs without monochromatic facial 3-paths
- Planar graphs without adjacent cycles of length at most five are (1,1,0)-colorable
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)
