2023/05/30 by János Barát, Barát, János, Zoltán L. Blázsik +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2305.19050
openalex publication_date 2023/05/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
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.