Kelly–Kühn–Osthus conjecture on directed cycle semidegree thresholds
Kelly–Kühn–Osthus conjecture on directed cycle semidegree thresholds
An oriented graph is a directed graph without loops or multiple edges. For an oriented graph , let be its minimum semidegree, the smaller of its minimum indegree and minimum outdegree. For an integer , let be the smallest integer greater than that does not divide . Kelly–Kühn–Osthus conjecture. For every there exists such that every oriented graph on vertices with
contains a directed cycle of length exactly . The conjectured threshold is best possible up to the stated additive term, as shown by balanced blow-ups of a directed -cycle. The conjecture is proved when ; the paper resolves the remaining cases for cycles of length divisible by but not equal to .
Sources & referencesView supporting material
Primary source
Andrzej Grzesik and Jan Volec, “Degree conditions forcing directed cycles”, arXiv:2102.12830 (2024).
Additional references
2 papers in this index state this conjecture (2011–2021). The statement above is taken from the most recent of them; the others are arXiv:1110.5669.
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.