The traceability conjecture for k-traceable oriented graphs

A digraph DD is kk-traceable if its order is at least kk and each of its induced subdigraphs of order kk is traceable; an oriented graph is a digraph obtained by orienting the edges of an undirected graph, and a digraph is traceable if it contains a hamiltonian directed path.

Traceability conjecture. For every integer k2k\geq 2, every kk-traceable oriented graph of order at least 2k12k-1 is traceable.

This conjecture extends Rédei's theorem that every tournament is traceable and strengthens results for strongly connected digraphs with independence number two. Its resolution status is not established by the supplied source material.

Sources & referencesView supporting material

Primary source

Bin Chen, Stefanie Gerke, Gregory Gutin, Hui Lei, Heis Parker-Cox and Yacong Zhou, “On the k-anti-traceability Conjecture”, arXiv:2403.19312 (2024).

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.