A smaller planar graph without 4-, 5-cycles and intersecting triangles that is not 3-choosable
In 2006, Montassier et al. constructed a planar graph without 4-, 5-cycles and intersecting triangles that is not 3-choosable [M. Montassier, A. Raspaud, W. Wang, Bordeaux 3-color conjecture and 3-choosability, Discrete Math. 306 (2006) 573-579]. It has 506 vertices. In this paper, we construct a smaller planar graph with the same properties. The planar graph has 380 vertices. (C) 2008 Elsevier B.V. All rights reserved.
planar graph 3-choosable combinatorial problems list coloring