Seminář G²OAT: Subgraphs with a positive minimum semidegree in digraphs with large outdegree

Abstrakt

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.

Další události