Planar graphs without 5-cycles and intersecting triangles are (1,1,0)-colorable

摘要

A (c(1), c(2), ... , c(k))-coloring of G is a mapping phi : V(G) over right arrow {1, 2, ... , k} such that for every i, 1 <= i <= k, G[V-i] has maximum degree at most c1, where G[V-i] denotes the subgraph induced by the vertices colored i. Borodin and Raspaud conjecture that every planar graph without 5-cycles and intersecting triangles is (0, 0, 0)-colorable. We prove in this paper that such graphs are (1, 1, 0)-colorable. (C) 2015 Elsevier B.V. All rights reserved.