Thomassé's path-length conjecture for oriented graphs
Thomassé's path-length conjecture for oriented graphs
An oriented graph is a digraph without 2-cycles. Let and be positive integers, and let be the minimum integer such that every oriented graph of girth and minimum outdegree at least contains a directed path of length . Thomassé's conjecture.
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
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.