Premium
Arc‐disjoint in‐ and out‐branchings in digraphs of independence number at most 2
Author(s) -
BangJensen Jørgen,
Bessy Stéphane,
Havet Frédéric,
Yeo Anders
Publication year - 2022
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22779
Subject(s) - digraph , independence number , combinatorics , mathematics , disjoint sets , conjecture , arc (geometry) , independence (probability theory) , discrete mathematics , graph , geometry , statistics
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.