A normal k-edge-coloring of a cubic graph is a proper edge-coloring with k colors having the additional property that when looking at the set of colors assigned to any edge e and the four edges adjacent to it, we have either exactly five distinct colors or exactly three distinct colors. We denote by chi N '(G) the smallest k, for which G admits a normal k-edge-coloring. Normal k-edge-colorings were introduced by Jaeger to study his well-known Petersen Coloring Conjecture. More precisely, it is known that proving chi N '(G)<= 5 for every bridgeless cubic graph is equivalent to proving the Petersen Coloring Conjecture and then it implies, among others, Cycle Double Cover Conjecture and Berge-Fulkerson Conjecture. Considering the larger class of all simple cubic graphs (not necessarily bridgeless), some interesting questions naturally arise. For instance, there exist simple cubic graphs, not bridgeless, with chi N '(G)=7. In contrast, the known best general upper bound for chi N '(G) was 9. Here, we improve it by proving that chi N '(G)<= 7 for any simple cubic graph G, which is best possible. We obtain this result by proving the existence of specific nowhere zero Z22-flows in 4-edge-connected graphs.
Normal edge‐colorings of cubic graphs / Mazzuoccolo, Giuseppe; Mkrtchyan, Vahan. - In: JOURNAL OF GRAPH THEORY. - ISSN 0364-9024. - 94:1(2020), pp. 75-91. [10.1002/jgt.22507]
Normal edge‐colorings of cubic graphs
Giuseppe Mazzuoccolo;Vahan Mkrtchyan
2020
Abstract
A normal k-edge-coloring of a cubic graph is a proper edge-coloring with k colors having the additional property that when looking at the set of colors assigned to any edge e and the four edges adjacent to it, we have either exactly five distinct colors or exactly three distinct colors. We denote by chi N '(G) the smallest k, for which G admits a normal k-edge-coloring. Normal k-edge-colorings were introduced by Jaeger to study his well-known Petersen Coloring Conjecture. More precisely, it is known that proving chi N '(G)<= 5 for every bridgeless cubic graph is equivalent to proving the Petersen Coloring Conjecture and then it implies, among others, Cycle Double Cover Conjecture and Berge-Fulkerson Conjecture. Considering the larger class of all simple cubic graphs (not necessarily bridgeless), some interesting questions naturally arise. For instance, there exist simple cubic graphs, not bridgeless, with chi N '(G)=7. In contrast, the known best general upper bound for chi N '(G) was 9. Here, we improve it by proving that chi N '(G)<= 7 for any simple cubic graph G, which is best possible. We obtain this result by proving the existence of specific nowhere zero Z22-flows in 4-edge-connected graphs.File | Dimensione | Formato | |
---|---|---|---|
finalversion.pdf
Accesso riservato
Dimensione
308.9 kB
Formato
Adobe PDF
|
308.9 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Pubblicazioni consigliate
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris