8 papers
Complexity of Arc-Decompositions involving Perfect Matchings and Cycle Factors
Hangning Liu, Jørgen Bang-Jensen, Jin Yan +1
For two digraph properties and , a -arc-decomposition of a digraph is a partition such that the spanning subdigraphs $D[A_…
Sparse spanning -strong oriented subdigraphs in split digraphs
Jia Zhou, Jørgen Bang-Jensen, Jin Yan
Jackson and Thomassen conjectured that every -strong digraph admits a spanning -strong oriented subdigraph [Ann. N. Y. Acad. Sci. 555 (1989) 402-412]. The conjecture holds f…
Highly connected spanning oriented subdigraphs in generalizations of semicomplete digraphs
Jia Zhou, Jørgen Bang-Jensen, Tong Zhou +1
Let be a positive integer. Jackson and Thomassen conjectured in 1989 that there exists an integer function such that every -strong digraph admits a spanning -st…
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…
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 , the inversion of a subset of vertices consists in reversing the orientation of all arcs with both endpoints in . When the subset is of size…
Acyclic dichromatic number of oriented graphs
Jørgen Bang-Jensen, Lucas Picasarri-Arrieta, Anders Yeo
The dichromatic number of a digraph is the minimum number of sets in a partition of into subsets so that the induced subdigraph $D[…