A relaxation of the Bordeaux Conjecture

2014/07/19 by Runrun Liu, Liu, Runrun, Xiangwen Li +3
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO

paper · pdf · doi:10.48550/arxiv.1407.5138

The paper is accepted by European Journal of Combinatorics for publication

arxiv created 2015/04/06 · arxiv updated 2015/04/07

Abstract

A (c₁,c₂,...,c_k)-coloring of G is a mapping φ:V(G)↦\1,2,...,k\ such that for every i,1 ≤ i ≤ k, G[V_i] has maximum degree at most c_i, where G[V_i] denotes the subgraph induced by the vertices colored i. Borodin and Raspaud conjecture that every planar graph without intersecting triangles and 5-cycles is 3-colorable. We prove in this paper that every planar graph without intersecting triangles and 5-cycles is (2,0,0)-colorable.

Related

• A relaxation of the strong Bordeaux Conjecture
• Planar graphs without 5-cycles and intersecting triangles are (1,1,0)-colorable
• A relaxation of Steinberg's Conjecture
• Relaxation of Wegner's Planar Graph Conjecture for maximum degree 4
• On the cyclic coloring conjecture