A linear lower bound for directed-path length in terms of girth and minimum out-degree
Statement
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.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.