PulseExploreJournal ClubDebatesTrendingResearchersJournals
Instagram
HomeExploreJournal ClubTrending
Synapse
⌘+K
Synapse
September 24, 20250 citationsOpen Access

Normal 6-edge-colorings of cubic graphs with oddness 2

View Full Paper
IFIgor FabriciBLBorut LužarRSRoman Soták

Key Points

  • Every cubic graph with oddness 2 admits a normal edge-coloring using at most 6 colors.
  • This finding builds on previous work demonstrating edge-coloring in cycle permutation graphs.
  • The conjecture that 5 colors are sufficient for normal edge-coloring remains a significant open question.
  • The results support the broader implications of the Petersen Coloring Conjecture in graph theory.

Abstract

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.

Ask AI
Helpful
Bookmark
Share
View Full Paper

Cite This Study

Fabrici et al. (2025) studied this question.

synapsesocial.com/papers/68d6e0fc8b2b6861e4c3f4eehttps://doi.org/10.48550/arxiv.2508.20565
Ask AI
Helpful
Bookmark
Share
View Full Paper