2021/04/19 by Mattiolo, Davide, Mazzuoccolo, Giuseppe, Mkrtchyan, Vahan
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2104.09241
If f:ℕ→ ℕ is a function, then let us say that f is sublinear if limn→ +∞(f(n))/(n)=0. If G=(V,E) is a cubic graph and c:E→ \1,...,k\ is a proper k-edge-coloring of G, then an edge e=uv of G is poor (rich) in c, if the edges incident to u and v are colored with three (five) colors. An edge is abnormal if it is neither rich nor poor. The Petersen coloring conjecture of Jaeger states that any bridgeless cubic graph admits a proper 5-edge-coloring c, such that there is no an abnormal edge of G with respect to c. For a proper 5-edge-coloring c of G, let NG(c) be the set of abnormal edges of G with respect to c. In this paper we show that (a) The Petersen coloring conjecture is equivalent to the statement that there is a sublinear function f:ℕ→ ℕ, such that all bridgeless cubic graphs admit a proper 5-edge-coloring c with |NG(c)|≤ f(|V|); (b) for k=2,3,4, the statement that there is a sublinear function f:ℕ→ ℕ, such that all (cyclically) k-edge-connected cubic graphs admit a proper 5-edge-coloring c with |NG(c)|≤ f(|V|) is equivalent to the statement that all (cyclically) k-edge-connected cubic graphs admit a proper 5-edge-coloring c with |NG(c)|≤ 2k+1.