Three-coloring planar graphs without short cycles

DOI10.1016/j.ipl.2006.08.009zbMath1185.05057OpenAlexW2051041659MaRDI QIDQ845915

Min Chen, Wei Fan Wang, Andre Raspaud

Publication date: 29 January 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2006.08.009

zbMATH Keywords

planar graphcoloringwithout odd cycles

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)

Related Items (max. 100)

On 3-colorable planar graphs without cycles of four lengths ⋮ Characterization of Cycle Obstruction Sets for Improper Coloring Planar Graphs ⋮ A step towards the strong version of Havel's three color conjecture ⋮ Short proofs of coloring theorems on planar graphs ⋮ Planar graphs without 4, 6, 8-cycles are 3-colorable ⋮ On 3-colorable planar graphs without short cycles ⋮ On the 3-colorability of planar graphs without 4-, 7- and 9-cycles

Cites Work

• On 3-colorable plane graphs without 5- and 7-cycles
• Planar graphs without cycles of length from 4 to 7 are 3-colorable
• A note on the three color problem
• A note on 3-choosability of planar graphs without certain cycles
• Structural properties of plane graphs without adjacent triangles and an application to 3-colorings
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Three-coloring planar graphs without short cycles