Strong orientation of a connected graph for a crossing family

Abdi, AhmadORCID logo; Dalirrooyfarda, Mahsa; and Neuwohner, MeikeORCID logo (2025) Strong orientation of a connected graph for a crossing family. Operations Research Letters. ISSN 0167-6377 (In press)
Copy

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).

mail Request Copy

picture_as_pdf
subject
Accepted Version
lock_clock
Restricted to Repository staff only until 1 January 2100
Available under Creative Commons: Attribution 4.0

Request Copy

Atom BibTeX OpenURL ContextObject in Span OpenURL ContextObject Dublin Core MPEG-21 DIDL Data Cite XML EndNote HTML Citation METS MODS RIOXX2 XML Reference Manager Refer ASCII Citation
Export

Downloads