@article{77953a811991489e8988a21c9c8a948c,
title = "Arc-disjoint in- and out-branchings in digraphs of independence number at most 2",
abstract = "We prove that every digraph of independence number at most 2 and arc‐connectivity at least 2 has an out‐ branching B+ and an in‐branching B− which are arc‐ disjoint (we call such branchings a good pair). This is best possible in terms of the arc‐connectivity as there are infinitely many strong digraphs with independence number 2 and arbitrarily high minimum in‐ and out‐ degrees that have no good pair. The result settles a conjecture by Thomassen for digraphs of independence number 2. We prove that every digraph on at most 6 vertices and arc‐connectivity at least 2 has a good pair and give an example of a 2‐arc‐strong digraph D on 10 vertices with independence number 4 that has no good pair. We also show that there are infinitely many digraphs with independence number 7 and arc‐ connectivity 2 that have no good pair. Finally we pose a number of open problems.",
keywords = "arc-connectivity, arc-disjoint branchings, digraphs of independence number 2, in-branching, out-branching",
author = "J{\o}rgen Bang-Jensen and St{\'e}phane Bessy and Fr{\'e}d{\'e}ric Havet and Anders Yeo",
note = "Funding Information: The authors thank Carsten Thomassen for interesting discussions on arc‐disjoint in‐ and out‐branchings in digraphs of bounded independence number. J. Bang‐Jensen research was supported by the Independent Research Fond Denmark under grant no. DFF 7014‐00037B, by PICS project DISCO, and by research grant ANR DIGRAPHS no. 194718. Part of this study was done while the author was visiting LIRMM, Universit{\'e} de Montpellier as well as INRIA Sophia Antipolis. Hospitality and financial support by both is gratefully acknowledged. Ce travail a b{\'e}n{\'e}fici{\'e} d'une aide du gouvernement fran{\c c}ais, g{\'e}r{\'e}e par l'Agence Nationale de la Recherche au titre du projet Investissements d'Avenir UCAJEDI portant la r{\'e}f{\'e}rence no. ANR‐15‐IDEX‐01. Part of this study was done while A. Yeo was visiting LIRMM, Universit{\'e} de Montpellier. Hospitality and financial support are gratefully acknowledged. Publisher Copyright: {\textcopyright} 2021 Wiley Periodicals LLC",
year = "2022",
month = jun,
doi = "10.1002/jgt.22779",
language = "English",
volume = "100",
pages = "294--314",
journal = "Journal of Graph Theory",
issn = "0364-9024",
publisher = "Wiley",
number = "2",
}