A comment to: On 3-colorable planar graphs without short cycles

2008/10/20 by Saieed Akbari, S. Akbari, Akbari, S. +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Computational Geometry and Mesh Generation #math.CO

paper · pdf · doi:10.48550/arxiv.0810.3298

2 pages

arxiv created 2008/10/20 · arxiv updated 2009/12/01

Abstract

Let G be a graph. It was proved that if G is a planar graph without 4, 6, 7-cycles and without two 5-cycles sharing exactly one edge, then G 3-colorable. We observed that the proof of this result is not correct.

Related

• Plane graphs without 4- and 5-cycles and without ext-triangular 7-cycles are 3-colorable
• Every planar graph without adjacent short cycles is 3-colorable
• Planar graphs having no cycle of length 4, 6 or 8 are DP-3-colorable
• DP-3-colorability of planar graphs without cycles of length 4, 7 or 9
• (1,0,0)-colorability of planar graphs without cycles of length 4 or 6