2019/11/15 by Ligang Jin, Jin, Ligang, Yingli Kang +1
Computer Science · Mathematics · #05C70 #Advanced Graph Theory Research #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1911.06759
openalex publication_date 2019/11/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In a proper edge-coloring of a cubic graph, an edge e is normal if the set of colors used by the edges adjacent to e has cardinality 3 or 5. The Petersen coloring conjecture asserts that every bridgeless cubic graph has a normal 5-edge-coloring, that is, a proper 5-edge-coloring such that all edges are normal. In this paper, we prove a result related to the Petersen coloring conjecture. The parameter μ3 is a measurement for cubic graphs, introduced by Steffen in 2015. Our result shows that every bridgeless cubic graph G has a proper 5-edge-coloring such that at least |E(G)|-μ3(G), which is no less than (4)/(5)|E(G)|, many edges are normal. This result improves on some earlier results of B'ılková and Šámal.