Normal edge-colorings of cubic graphs
share
A normal k-edge-coloring of a cubic graph is an 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 it, we have either exactly five distinct colors or exactly three distinct colors. We denote by χ'_N(G) the smallest k, for which G admits a normal k-edge-coloring. Normal k-edge-colorings were introduced by Jaeger in order to study his well-known Petersen Coloring Conjecture. More precisely, it is known that proving χ'_N(G)≤ 5 for every bridgeless cubic graph is equivalent to proving Petersen Coloring Conjecture and then, 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 χ'_N(G)=7. On the other hand, the known best general upper bound for χ'_N(G) was 9. Here, we improve it by proving that χ'_N(G)≤7 for any simple cubic graph G, which is best possible. We obtain this result by proving the existence of specific no-where zero Z_2^2-flows in 4-edge-connected graphs.
READ FULL TEXT