A sufficient condition for planar graphs to be 3-colorable
From MaRDI portal
Publication:1405097
The authors prove that every proper 3-coloring of a face of size 3 or 7 in a connected planar graph without pairs of 3-cycles at distance less than 4 and without 5-cycles can be extended to a proper 3-coloring of the whole graph. Form this and Grötzsch's theorem, it follows that planar graphs without 3-cycles at distance less than 4 and without 5-cycles are 3-colorable. The authors conjecture that planar graphs without 5-cycles in which every two 3-cycles are vertex-disjoint (or every two 3-cycles are edge-disjoint) are 3-colorable.
Recommendations
- Planar graphs without cycles of length from 4 to 7 are 3-colorable
- A sufficient condition for a planar graph to be 3-colorable
- Planar graphs without triangles adjacent to cycles of length from 3 to 9 are 3-colorable
- On 3-colorable planar graphs without short cycles
- Planar graphs without 5- and 7-cycles and without adjacent triangles are 3-colorable
Cites work
Cited in
(41)- A structural theorem on embedded graphs and its application to colorings
- Planar graphs without adjacent cycles of length at most seven are 3-colorable
- A condition for assured 3-face-colorability of infinite plane graphs with a given spanning tree
- Planar graphs without 3-cycles adjacent to cycles of length 3 or 5 are \((3, 1)\)-colorable
- A step towards the strong version of Havel's three color conjecture
- Fast 3-coloring triangle-free planar graphs
- Planar graphs without adjacent cycles of length at most five are (2, 0, 0)-colorable
- Three-coloring triangle-free graphs on surfaces. V: Coloring planar graphs with distant anomalies
- A relaxation of Novosibirsk 3-color conjecture
- Building a maximal independent set for the vertex-coloring problem on planar graphs
- Every planar graph without triangles adjacent to cycles of length 3 or 6 is \(( 1 , 1 , 1 )\)-colorable
- 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
- Planar graphs without cycles of lengths 4 and 5 and close triangles are DP-3-colorable
- Every planar graph without adjacent cycles of length at most 8 is 3-choosable
- Extending colorings of planar graphs
- A relaxation of the Bordeaux conjecture
- Bordeaux 3-color conjecture and 3-choosability
- Continuation of a 3-coloring from a 7-face onto a plane graph without \(C_3\)
- A 3-color theorem on plane graphs without 5-circuits
- Three coloring planar graphs without cycles of length from 4 to 6 or seven cycles with close triangles
- A condition for the three colourability of planar locally path graphs
- Planar graphs with neither 5-cycles nor close 3-cycles are 3-colorable
- A sufficient condition for 3-colorable plane graphs
- Steinberg's conjecture is false
- A NOTE ON 3-COLORABLE PLANE GRAPHS WITHOUT 5- AND 7-CYCLES
- Decomposing a planar graph without cycles of length 5 into a matching and a 3-colorable graph
- A sufficient condition on 3-colorable plane graphs without 5- and 6-circuits
- scientific article; zbMATH DE number 2097483 (Why is no real title available?)
- Distance constraints on short cycles for 3-colorability of planar graphs
- A sufficient condition for a planar graph to be 3-colorable
- Planar graphs without cycles of length 4 or 5 are (7 : 2)-colorable
- On the strong Bordeaux conjecture
- Acyclically 3-colorable planar graphs
- On 3-colorings of plane graphs
- Planar graphs without triangles adjacent to cycles of length from 4 to 7 are 3-colorable
- The independence ratio of 4-cycle-free planar graphs
- Planar graphs without adjacent cycles of length at most five are (1,1,0)-colorable
- A counterexample to the conjecture of Aksionov and Mel'nikov on non-3- colorable planar graphs
- On 3-colorable plane graphs without 5- and 7-cycles
- A non-3-choosable planar graph without cycles of length 4 and 5
This page was built for publication: A sufficient condition for planar graphs to be 3-colorable
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1405097)
