Normal 5‐Edge‐Colorings and Perfect Matching Covers of Cubic Graphs

ABSTRACT

The Petersen coloring conjecture and its equivalent version, the normal 5‐edge‐coloring conjecture, was proposed by Jaeger in 1980 and 1985, respectively. This conjecture implies several major conjectures in graph theory, including the cycle double cover conjecture, the Berge–Fulkerson conjecture, and the Alon–Tarsi shortest cycle cover conjecture. Nevertheless, the existence of a Petersen coloring or a normal 5‐edge‐coloring of a cubic graph does not determine the exact value of the perfect matching cover index , defined as the minimum number of perfect matchings needed to cover all edges of . In this article, we investigate the relationship between Petersen colorings (equivalently, normal 5‐edge‐colorings) and the perfect matching cover index. We present two sufficient conditions under which . We also provide a characterization of graphs with , which reveals a connection between 4‐perfect‐matching covers and nowhere‐zero 4‐flows.