Steinberg's conjecture is false
From MaRDI portal
Publication:345097
DOI10.1016/j.jctb.2016.07.006zbMath1350.05018arXiv1604.05108OpenAlexW2963985217WikidataQ105319014 ScholiaQ105319014MaRDI QIDQ345097
Daniel Král', Vincent Cohen-Addad, Zhentao Li, Esteban Salgado, Michael Hebdige
Publication date: 25 November 2016
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
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)
Related Items (max. 100)
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 ⋮ Further extensions of the Grötzsch theorem ⋮ Circular backbone colorings: on matching and tree backbones of planar graphs ⋮ The Strong Fractional Choice Number and the Strong Fractional Paint Number of Graphs ⋮ Defective 2-colorings of planar graphs without 4-cycles and 5-cycles ⋮ 3-Paintability of planar graphs ⋮ Hyperbolic families and coloring graphs on surfaces ⋮ Characterization of Cycle Obstruction Sets for Improper Coloring Planar Graphs ⋮ Choosability with union separation of planar graphs without cycles of length 4 ⋮ 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 ⋮ Every signed planar graph without cycles of length from 4 to 8 is 3-colorable ⋮ Circular coloring and fractional coloring in planar graphs ⋮ Plane Graphs without 4- and 5-Cycles and without Ext-Triangular 7-Cycles are 3-Colorable ⋮ Mapping sparse signed graphs to (K2k,M) $({K}_{2k},M)$ ⋮ Every planar graph without 4-cycles and 5-cycles is (3,3)-colorable ⋮ Planar graphs without 3-cycles adjacent to cycles of length 3 or 5 are \((3, 1)\)-colorable ⋮ Fractional coloring planar graphs under Steinberg-type conditions ⋮ Planar graphs without 5-cycles and intersecting triangles are \((1, 1, 0)\)-colorable ⋮ 1-planar graphs with girth at least 6 are (1,1,1,1)-colorable ⋮ Square Coloring Planar Graphs with Automatic Discharging ⋮ 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 ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Partitioning planar graphs without 4-cycles and 5-cycles into bounded degree forests ⋮ Gaps in the cycle spectrum of 3-connected cubic planar graphs ⋮ Steinberg-like theorems for backbone colouring ⋮ An introduction to the discharging method via graph coloring ⋮ Flexibility of planar graphs -- sharpening the tools to get lists of size four ⋮ Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8 ⋮ 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 ⋮ Decomposing a planar graph without triangular 4-cycles into a matching and a 3-colorable graph ⋮ Planar graphs without 4-cycles and close triangles are \((2,0,0)\)-colorable ⋮ Every planar graph without 5-cycles and \(K_4^-\) and adjacent 4-cycles is \((2, 0, 0)\)-colorable ⋮ A refinement of choosability of graphs ⋮ Note on improper coloring of $1$-planar graphs ⋮ Planar graphs without adjacent cycles of length at most five are \((1,1,0)\)-colorable ⋮ Backbone coloring of graphs with galaxy backbones ⋮ \((1,0,0)\)-colorability of planar graphs without cycles of length \(4\) or \(6\) ⋮ A relaxation of Novosibirsk 3-color conjecture ⋮ 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 ⋮ 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
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Planar graphs without triangles adjacent to cycles of length from 4 to 7 are 3-colorable
- On 3-colorable plane graphs without 5- and 7-cycles
- A non-3-choosable planar graph without cycles of length 4 and 5
- Planar graphs without 5- and 7-cycles and without adjacent triangles are 3-colorable
- 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
- Colorings of plane graphs: a survey
- Planar graphs without triangles adjacent to cycles of length from 3 to 9 are 3-colorable
- Structural properties of plane graphs without adjacent triangles and an application to 3-colorings
This page was built for publication: Steinberg's conjecture is false
