Long directed paths in Eulerian digraphs

MaRDI QIDQ6359210zbMATH OpenFDO

Authors Oliver Janzer, Benny Sudakov, István Tomon

Publication date 27 January 2021

Abstract: An old conjecture of Bollob'as and Scott asserts that every Eulerian directed graph with average degree $d$ contains a directed cycle of length at least $Omega(d)$. The best known lower bound for this problem is $Omega(d^{1/2})$ by Huang, Ma, Shapira, Sudakov and Yuster. They asked whether this estimate can be improved at least for directed paths instead of cycles and whether one can find a long path starting from any vertex if the host digraph is connected. In this paper we break the $sqrtd$ barrier, showing how to find a path of length $Omega(d^{1/2+1/40})$ from any vertex of a connected Eulerian digraph.

This page was built for publication: Long directed paths in Eulerian digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6359210)