The traceability conjecture for k-traceable oriented graphs
The traceability conjecture for k-traceable oriented graphs
A digraph is -traceable if its order is at least and each of its induced subdigraphs of order 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 , every -traceable oriented graph of order at least 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
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.