A linear lower bound for directed-path length in terms of girth and minimum out-degree
A linear lower bound for directed-path length in terms of girth and minimum out-degree
For a digraph , let be the length of a longest directed path, let be its girth, and let be its minimum out-degree. Proposed weaker Thomassé conjecture. There is some constant such that
for every digraph .
This conjecture weakens Thomassé's proposed bound and is motivated by the paper's lower bounds for regular digraphs. The supplied text does not state whether it is known or remains open, so its database status is left open.
Sources & referencesView supporting material
Primary source
Yangyang Cheng and Peter Keevash, “On the length of directed paths in digraphs”, arXiv:2402.16776 (2024).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.