Article ID Journal Published Year Pages File Type
4646695 Discrete Mathematics 2016 12 Pages PDF
Abstract

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

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