2025/08/28 by Igor Fabrici, Fabrici, Igor, Borut Lužar +5
Computer Science · Engineering · #05C15 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2508.20565
openalex publication_date 2025/08/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A normal edge-coloring of a cubic graph is a proper edge-coloring, in which every edge is adjacent to edges colored with four distinct colors or to edges colored with two distinct colors. It is conjectured that 5 colors suffice for a normal edge-coloring of any bridgeless cubic graph and this statement is equivalent to the Petersen Coloring Conjecture. In this paper, we extend the result of Mazzuoccolo and Mkrtchyan (Normal 6-edge-colorings of some bridgeless cubic graphs, Discrete Appl. Math. 277 (2020), 252--262), who proved that every cycle permutation graph admits a normal edge-coloring with at most 6 colors. In particular, we show that every cubic graph with oddness 2 admits a normal edge-coloring with at most 6 colors.