2015/08/31 by Ziwen Huang, Huang, Ziwen, Xiangwen Li +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Digital Image Processing Techniques #FOS: Mathematics #Limits and Structures in Graph Theory #math.CO
paper · pdf · doi:10.48550/arxiv.1508.07890
14 pages
arxiv created 2015/08/31 · openalex publication_date 2015/08/31 · arxiv updated 2015/09/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let c1, c2, ⋯, ck be k non-negative integers. A graph G is (c1, c2, ⋯, ck)-colorable if the vertex set can be partitioned into k sets V1,V2, …, Vk, such that the subgraph G[Vi], induced by Vi, has maximum degree at most ci 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+).