Planar graphs without 5-cycles and intersecting triangles are (1,1,0)-colorable

2014/09/14 by Runrun Liu, Liu, Runrun, Xiangwen Li +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #Computer graphics (images) #Computer science #Conjecture #FOS: Mathematics #Graph #Limits and Structures in Graph Theory #Mathematics #Planar #Planar graph #math.CO

paper · pdf · doi:10.48550/arxiv.1409.4054

openalex publication_date 2014/09/14 · arxiv created 2014/09/26 · arxiv updated 2014/09/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/06

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 5-cycles and intersecting triangles is (0,0,0)-colorable. We prove in this paper that such graphs are (1,1,0)-colorable.

Citations

• The State of the Three Color Problem

Related

• A relaxation of the Bordeaux Conjecture
• (1,0,0)-colorability of planar graphs without cycles of length 4 or 6
• A relaxation of Steinberg's Conjecture
• Vertex partitions of (C₃,C₄,C₆)-free planar graphs
• A relaxation of the strong Bordeaux Conjecture