Article ID Journal Published Year Pages File Type
6424156 European Journal of Combinatorics 2015 10 Pages PDF
Abstract

A (c1,c2,…,ck)-coloring of a graph G is a mapping φ:V(G)↦{1,2,…,k} such that for every i,1≤i≤k, G[Vi] has maximum degree at most ci, where G[Vi] denotes the subgraph induced by the vertices colored i. Borodin and Raspaud conjecture that every planar graph with neither 5-cycles nor intersecting triangles is 3-colorable. We prove in this paper that every planar graph with neither 5-cycles nor intersecting triangles is (2, 0, 0)-colorable.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , ,