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

Autor:	Barát, János, Blázsik, Zoltán L.
Rok vydání:	2023
Předmět:	Mathematics - Combinatorics
Druh dokumentu:	Working Paper
Popis:	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\"orsch 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$. Comment: 7 pages
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2305.19050 Zobrazit plný text záznamu View this record from Arxiv