A relaxation of the strong Bordeaux Conjecture

Original · EN

Let c₁, c₂,, cₖ be k non-negative integers. A graph G is (c₁, c₂,, cₖ)-colorable if the vertex set can be partitioned into k sets V₁,V₂,, Vₖ, such that the subgraph G[Vᵢ], induced by Vᵢ, has maximum degree at most cᵢ for i=1, 2,, k. Let F denote the family of plane graphs with neither adjacent 3-cycles nor 5-cycle. Borodin and Raspaud (2003) conjectured that each graph in F is (0,0,0)-colorable. In this paper, we prove that each graph in F is (1, 1, 0)-colorable, which improves the results by Xu (2009) and Liu-Li-Yu (2014+).