Jørgen Bang-Jensen

activity

20232026

collaborators

11 papers

math.CO2026

Highly connected uniquely $k$ -linked digraphs

Jørgen Bang-Jensen

Extending a result of Thomassen, we prove that for every choice of positive integers $K \geq k$ there exist a $K$ -strong digraph which has two disjoint sets $S, T$ each of size $k$ s…

math.CO2026

Degree conditions for $k$ -strong orientations of digraphs

Jørgen Bang-Jensen, Shuo Wei

Jackson and Thomassen conjectured that every $2 k$ -strong digraph contains a spanning $k$ -strong oriented subdigraph. We prove sharp degree conditions for the existence of such a su…

math.CO2026

Sharp connectivity thresholds for mixed rigidity packings and improved bounds for highly connected orientations of graphs

Hanzhi Bai, Jørgen Bang-Jensen, Jin Yan

Garamvölgyi, Jordán, Király and Villányi [{{\bf Forum Math. Pi} \textbf{13} (2025), Paper No.~e11}] posed two sharp connectivity conjectures for packing rigid spanning subgraphs: o…

math.CO2026

Complexity of Arc-Decompositions involving Perfect Matchings and Cycle Factors

Hangning Liu, Jørgen Bang-Jensen, Jin Yan +1

For two digraph properties $P_{1}$ and $P_{2}$ , a $(P_{1}, P_{2})$ -arc-decomposition of a digraph $D$ is a partition $A (D) = A_{1} \cup ˙ A_{2}$ such that the spanning subdigraphs $D[A_…

math.CO2026

Sparse spanning $k$ -strong oriented subdigraphs in split digraphs

Jia Zhou, Jørgen Bang-Jensen, Jin Yan

Jackson and Thomassen conjectured that every $2 k$ -strong digraph admits a spanning $k$ -strong oriented subdigraph [Ann. N. Y. Acad. Sci. 555 (1989) 402-412]. The conjecture holds f…

math.CO2026

Highly connected spanning oriented subdigraphs in generalizations of semicomplete digraphs

Jia Zhou, Jørgen Bang-Jensen, Tong Zhou +1

Let $k$ be a positive integer. Jackson and Thomassen conjectured in 1989 that there exists an integer function $f (k)$ such that every $f (k)$ -strong digraph admits a spanning $k$ -st…

math.CO2026

K-Arc-Strong Orientations Of Semicomplete Digraphs

Tong Zhou, Jørgen Bang-Jensen, Jia Zhou +1

Results by Jackson and Frank imply that every 2k-arc-strong digraph D contains a spanning k-arc-strong oriented subdigraph. This is best possible, even for very dense digraphs. A d…

math.CO2025

Making an oriented graph acyclic using inversions of bounded or prescribed size

Jørgen Bang-Jensen, Frédéric Havet, Florian Hörsch +3

Given an oriented graph $D$ , the inversion of a subset $X$ of vertices consists in reversing the orientation of all arcs with both endpoints in $X$ . When the subset $X$ is of size…

math.CO2025

Acyclic dichromatic number of oriented graphs

Jørgen Bang-Jensen, Lucas Picasarri-Arrieta, Anders Yeo

The dichromatic number $χ (D)$ of a digraph $D = (V, A)$ is the minimum number of sets in a partition $V_{1}, \dots, V_{k}$ of $V$ into $k$ subsets so that the induced subdigraph $D[V…

math.CO2025

On the $k$ -linkage problem for generalizations of semicomplete digraphs

Jia Zhou, Jørgen Bang-Jensen, Jin Yan

A directed graph (digraph) $D$ is $k$ -linked if $∣ D ∣ \geq 2 k$ , and for any $2 k$ distinct vertices $x_{1}, \dots, x_{k}, y_{1}, \dots, y_{k}$ of $D$ , there exist vertex-disjoi…

cs.DM2023

Constrained Flows in Networks

Stéphane Bessy, Jørgen Bang-Jensen, Lucas Picasarri-Arrieta

The support of a flow $x$ in a network is the subdigraph induced by the arcs $uv$ for which $x (uv) > 0$ . We discuss a number of results on flows in networks where we put certain rest…

Highly connected uniquely k-linked digraphs

Degree conditions for k-strong orientations of digraphs

Sharp connectivity thresholds for mixed rigidity packings and improved bounds for highly connected orientations of graphs

Complexity of Arc-Decompositions involving Perfect Matchings and Cycle Factors

Sparse spanning k-strong oriented subdigraphs in split digraphs

Highly connected spanning oriented subdigraphs in generalizations of semicomplete digraphs

K-Arc-Strong Orientations Of Semicomplete Digraphs

Making an oriented graph acyclic using inversions of bounded or prescribed size

Acyclic dichromatic number of oriented graphs

On the k-linkage problem for generalizations of semicomplete digraphs

Constrained Flows in Networks

Highly connected uniquely $k$ -linked digraphs

Degree conditions for $k$ -strong orientations of digraphs

Sparse spanning $k$ -strong oriented subdigraphs in split digraphs

On the $k$ -linkage problem for generalizations of semicomplete digraphs