2024/06/06 by Reich, Florian
#05C20 #05C40 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2406.03883
It is well-known that for every set U of vertices in a connected graph G there is either a subdivided star in G with a large number of leaves in U, or a comb in G with a large number of teeth in U. In this paper we extend this property to directed graphs. More precisely, we prove that for every n ∈ ℕ and every sufficiently large set U of vertices in a strongly connected directed graph D, there exists a strongly connected butterfly minor of D with n teeth in U that is either shaped by a star or shaped by a comb.