On sublinear approximations for the Petersen coloring conjecture

Abstract

If $f:\mathbb{N}\to \mathbb{N}$ is a function, then let us say that $f$ is sublinear if \[\lim_{n\rightarrow +\infty}\frac{f(n)}{n}=0.\] If $G=(V,E)$ is a cubic graph and $c:E\to \{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 $N_G(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:\mathbb{N}\to \mathbb{N}$, such that all bridgeless cubic graphs admit a proper 5-edge-coloring $c$ with $|N_G(c)|\le f(|V|)$; (b) for $k=2,3,4$, the statement that there is a sublinear function $f:\mathbb{N}\to \mathbb{N}$, such that all (cyclically) $k$-edge-connected cubic graphs admit a proper 5-edge-coloring $c$ with $|N_G(c)|\le f(|V|)$ is equivalent to the statement that all (cyclically) $k$-edge-connected cubic graphs admit a proper 5-edge-coloring $c$ with $|N_G(c)|\le 2k+1$.

10 pages, 4 figures