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

Barát, János and Blázsik, Zoltán L. (2024) Improved upper bound on the Frank number of 3-edge-connected graphs. EUROPEAN JOURNAL OF COMBINATORICS, 118. ISSN 0195-6698

Preview

Text 1-s2.0-S0195669823002317-main.pdf Available under License Creative Commons Attribution. Download (370kB) | Preview

Abstract

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

Actions (login required)

Edit Item