Planar graphs with neither 5-cycles nor close 3-cycles are 3-colorable

DOI10.1002/jgt.20486zbMath1237.05067OpenAlexW1996716402MaRDI QIDQ3067058

Alekseĭ Nikolaevich Glebov, Oleg V. Borodin

Publication date: 20 January 2011

Published in: Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/jgt.20486

zbMATH Keywords

planar graphscoloringHavel's problem

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)

Related Items (max. 100)

Facially-constrained colorings of plane graphs: a survey ⋮ A step towards the strong version of Havel's three color conjecture ⋮ Planar graphs without 5-cycles and intersecting triangles are \((1, 1, 0)\)-colorable ⋮ Decomposing a planar graph without cycles of length 5 into a matching and a 3-colorable graph ⋮ Distance constraints on short cycles for 3-colorability of planar graphs ⋮ Unnamed Item ⋮ Planar graphs without adjacent cycles of length at most five are (2, 0, 0)-colorable ⋮ 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 ⋮ Planar graphs without adjacent cycles of length at most five are \((1,1,0)\)-colorable ⋮ Planar graphs without cycles of lengths 4 and 5 and close triangles are DP-3-colorable ⋮ A relaxation of the Bordeaux conjecture

Cites Work

• On 3-colorable plane graphs without 5- and 7-cycles
• Planar graphs without 5- and 7-cycles and without adjacent triangles are 3-colorable
• 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
• 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
• A NOTE ON 3-COLORABLE PLANE GRAPHS WITHOUT 5- AND 7-CYCLES
• The color space of a graph
• Structural properties of plane graphs without adjacent triangles and an application to 3-colorings
• On a conjecture of B. Grünbaum
• Unnamed Item
• Unnamed Item

This page was built for publication: Planar graphs with neither 5-cycles nor close 3-cycles are 3-colorable