Subgraphs with a positive minimum semidegree in digraphs with large outdegree

Jan Volec, 8 Apr 2024

We show that every d-out-regular directed graph G has a subgraph that has the minimum semidegree at least d(d+1)/(2|V(G)|). On the other hand, for every c > 0 we construct infinitely many tournaments T with the minimum outdegree d and the property that every subgraph of T has the minimum semidegree at most (1+c)d(d+1)/(2|V(T)|).

This is a joint work with Andrzej Grzesik and Vojta Rödl.