On the Chudnovsky-Seymour-Sullivan Conjecture on Cycles in Triangle-free Digraphs

2009/09/14 by Kevin Chen, Chen, Kevin, Sean Karson +5 · 1 citation
Computer Science · Mathematics · #05C20 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #math.CO #msc:05C20

paper · pdf · doi:10.48550/arxiv.0909.2468

5 pages

arxiv created 2009/09/14 · openalex publication_date 2009/09/14 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

For a simple digraph G without directed triangles or digons, let β(G) be the size of the smallest subset X ⊆ E(G) such that G∖ X has no directed cycles, and let γ(G) be the number of unordered pairs of nonadjacent vertices in G. In 2008, Chudnovsky, Seymour, and Sullivan showed that β(G) ≤ γ(G), and conjectured that β(G) ≤ γ(G)/2. Recently, Dunkum, Hamburger, and Pór proved that β(G) ≤ 0.88 γ(G). In this note, we prove that β(G) ≤ 0.8616 γ(G).

Cited by

• Strong connectivity and directed triangles in oriented graphs. Partial results on a particular case of the Caccetta-Häggkvist conjecture

Related

• On the minimal feedback arc set of m-free Digraphs
• Directed graphs without short cycles
• Contributions to Seymour's Second Neighborhood Conjecture
• On Seymour's and Sullivan's Second Neighbourhood Conjectures
• A note on the second neighborhood problem for k-anti-transitive and m-free digraphs