The traceability conjecture for k-traceable oriented graphs
Statement
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.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.