Improved upper bound on the Frank number of $3$-edge-connected graphs

Abstract

In an orientation $O$ of the graph $G$, an arc $e$ is deletable if and only if $O-e$ is strongly connected. For a $3$-edge-connected graph $G$, the Frank number is the minimum $k$ for which $G$ admits $k$ strongly connected orientations such that for every edge $e$ of $G$ the corresponding arc is deletable in at least one of the $k$ orientations. Hörsch and Szigeti conjectured the Frank number is at most $3$ for every $3$-edge-connected graph $G$. We prove an upper bound of $5$, which improves the previous bound of $7$.

7 pages