Distance constraints on short cycles for 3-colorability of planar graphs
From MaRDI portal
Publication:497344
DOI10.1007/s00373-014-1476-3zbMath1321.05070OpenAlexW2069158404MaRDI QIDQ497344
Publication date: 24 September 2015
Published in: Graphs and Combinatorics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00373-014-1476-3
Paths and cycles (05C38) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Distance in graphs (05C12)
Related Items (max. 100)
Plane Graphs without 4- and 5-Cycles and without Ext-Triangular 7-Cycles are 3-Colorable ⋮ Planar graphs without adjacent cycles of length at most five are \((1,1,0)\)-colorable ⋮ \((1,0,0)\)-colorability of planar graphs without cycles of length \(4\) or \(6\)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Planar graphs without triangles adjacent to cycles of length from 4 to 7 are 3-colorable
- A relaxation of Havel's 3-color problem
- On 3-colorability of planar graphs without adjacent short cycles
- Planar graphs without adjacent cycles of length at most seven are 3-colorable
- Signed graphs
- Some simplified NP-complete graph problems
- 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
- A step towards the strong version of Havel's three color conjecture
- Colorings of plane graphs: a survey
- Planar graphs without triangles adjacent to cycles of length from 3 to 9 are 3-colorable
- A 3-color theorem on plane graphs without 5-circuits
- Planar graphs with neither 5-cycles nor close 3-cycles are 3-colorable
- Structural properties of plane graphs without adjacent triangles and an application to 3-colorings
- On a conjecture of B. Grünbaum
This page was built for publication: Distance constraints on short cycles for 3-colorability of planar graphs
