Thomassé's path-length conjecture for oriented graphs

An oriented graph is a digraph without 2-cycles. Let hh and gg be positive integers, and let l(h,g)l(h,g) be the minimum integer such that every oriented graph of girth gg and minimum outdegree at least hh contains a directed path of length l(h,g)l(h,g). Thomassé's conjecture.

l(h,g)h(g1).l(h,g)\geq h(g-1).

Sullivan attributed this conjecture to Thomassé and noted that it would imply the Caccetta–Häggkvist conjecture for oriented graphs. The paper disproves its even-girth case, so the conjecture as stated is refuted.

Sources & referencesView supporting material

Primary source

Yandong Bai and Yannis Manoussakis, “On the number of vertex-disjoint cycles in digraphs”, arXiv:1805.02999 (2018).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.