Improved upper bound on the Frank number of 3-edge-connected graphs
János Barát, Zoltán L. Blázsik · European Journal of Combinatorics · 2024
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.