ProbXiv
Explorersign in
Problem archiveProblem record

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

Added
Links

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 in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.