Exact feedback sets in cyclic tournament substitutions
Statement
Conjecture 6. 2 7. (Chudnovsky, Seymour, Sullivan) Let G be a simple digraph with k non-edges (unordered pairs {u, v } where both uv and vu are not in E(G)). If G has no directed cycle of length at most 3, one can delete at most k/ 2 edges from G and obtain a graph with no directed cycle. Notes: We know that there are tight examples for this conjecture (transitive tournaments, C4,and products of these). It is also known that a minimal counterexample has no source or sink vertex, and no directed cut. Kostochka recently proved all vertices in a minimal counterexample have at least 3 and at most ( n − 1) /2 non-neighbors. He has an argument using these facts to show the conjecture for all k ≤ 14.
Record
- Source
- Added
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.