J. Bang-Jensen

activity

20112024

most citedFinding an induced subdivision of a digraph

11 citations · 32 across the 21 of their papers we have counts for

collaborators

30 papers

math.CO2024

Generalized paths and cycles in semicomplete multipartite digraphs

Jørgen Bang-Jensen, Yun Wang, Anders Yeo

It is well-known and easy to show that even the following version of the directed travelling salesman problem is NP-complete: Given a strongly connected complete digraph $D = (V, A)$ ,…

math.CO2023

Complexity of (arc)-connectivity problems involving arc-reversals or deorientations

Jørgen Bang-Jensen, Florian Hörsch, Matthias Kriesell

By a well known theorem of Robbins, a graph $G$ has a strongly connected orientation if and only if $G$ is 2-edge-connected and it is easy to find, in linear time, either a cut edg…

math.CO2021★ 1 cited

Every $(13 k - 6)$ -strong tournament with minimum out-degree at least $28 k - 13$ is $k$ -linked

Jørgen Bang-Jensen, Kasper Skov Johansen

A digraph $D$ is $k$ -linked if it satisfies that for every choice of disjoint sets ${x_{1}, \dots, x_{k}}$ and ${y_{1}, \dots, y_{k}}$ of vertices of $D$ there are vertex disjoint pa…

math.CO2021★ 7 cited

On the inversion number of oriented graphs

Jørgen Bang-Jensen, Jonas Costa Ferreira da Silva, Frédéric Havet

Let $D$ be an oriented graph. The inversion of a set $X$ of vertices in $D$ consists in reversing the direction of all arcs with both ends in $X$ . The inversion number of $D$ , deno…

math.CO2020

Digraphs and variable degeneracy

Jørgen Bang-Jensen, Thomas Schweser, Michael Stiebitz

Let $D$ be a digraph, let $p \geq 1$ be an integer, and let $f : V (D) \to N_{0}^{p}$ be a vector function with $f = (f_{1}, f_{2}, \dots, f_{p})$ . We say that $D$ has an $f$ -partition if…

math.CO2020★ 1 cited

Low chromatic spanning sub(di)graphs with prescribed degree or connectivity properties

J. Bang-Jensen, F. Havet, M. Kriesell +1

Generalizing well-known results of Erdős and Lovász, we show that every graph $G$ contains a spanning $k$ -partite subgraph $H$ with $λ (H) \geq ⌈ \frac{k - 1}{k} λ (G)⌉$ , wher…