← All problems

Thomassé's path-length conjecture for oriented graphs

7 years old · documented by

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(g−1).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.

References

Status

  • Refuted: Yandong Bai and Yannis Manoussakis. On the number of vertex-disjoint cycles in digraphs (arXiv (arXiv:1805.02999), 2018) https://arxiv.org/abs/1805.02999

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.