2024/03/04 by Pierre Aboulker, Frédéric Havet, Aboulker, Pierre +5
Computer Science · Mathematics · #05C20 #05C55 #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph theory and applications
paper · pdf · doi:10.48550/arxiv.2403.02298
openalex publication_date 2024/03/04 · openalex created_date 2024/03/06 · openalex updated_date 2026/08/01
Let D be a digraph. Its acyclic number α(D) is the maximum order of an acyclic induced subdigraph and its dichromatic number χ(D) is the least integer k such that V(D) can be partitioned into k subsets inducing acyclic subdigraphs. We study a(n) and t(n) which are the minimum of α(D) and the maximum of χ(D), respectively, over all oriented triangle-free graphs of order n. For every ε>0 and n large enough, we show (1/√(2) - ε) √(nlog n) ≤ a(n) ≤ (107)/(8) √ n log n and (8)/(107) √ n/log n ≤ t(n) ≤ (√ 2 + ε) √(n/log n). We also construct an oriented triangle-free graph on 25 vertices with dichromatic number~3, and show that every oriented triangle-free graph of order at most 17 has dichromatic number at most 2.