2024/11/20 by Ahmad Abdi, Abdi, Ahmad, Dalirrooyfard, Mahsa +2
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Graph Labeling and Dimension Problems
paper · pdf · doi:10.48550/arxiv.2411.13202
openalex publication_date 2024/11/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given a connected graph G=(V,E) and a crossing family C over ground set V such that |δG(U)|≥ 2 for every U∈ C, we prove there exists a strong orientation of G for C, i.e., an orientation of G such that each set in C has at least one outgoing and at least one incoming arc. This implies the main conjecture in Chudnovsky et al. (Disjoint dijoins. Journal of Combinatorial Theory, Series B, 120:18--35, 2016). In particular, in every minimal counterexample to the Edmonds-Giles conjecture where the minimum weight of a dicut is 2, the arcs of nonzero weight must be disconnected.