Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2411.13202 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913581874806784 |
|---|---|
| author | Abdi, Ahmad Dalirrooyfard, Mahsa Neuwohner, Meike |
| author_facet | Abdi, Ahmad Dalirrooyfard, Mahsa Neuwohner, Meike |
| contents | Given a connected graph $G=(V,E)$ and a crossing family $\mathcal{C}$ over ground set $V$ such that $|δ_G(U)|\geq 2$ for every $U\in \mathcal{C}$, we prove there exists a strong orientation of $G$ for $\mathcal{C}$, i.e., an orientation of $G$ such that each set in $\mathcal{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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_13202 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Strong orientation of a connected graph for a crossing family Abdi, Ahmad Dalirrooyfard, Mahsa Neuwohner, Meike Combinatorics Given a connected graph $G=(V,E)$ and a crossing family $\mathcal{C}$ over ground set $V$ such that $|δ_G(U)|\geq 2$ for every $U\in \mathcal{C}$, we prove there exists a strong orientation of $G$ for $\mathcal{C}$, i.e., an orientation of $G$ such that each set in $\mathcal{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. |
| title | Strong orientation of a connected graph for a crossing family |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2411.13202 |