Covering the edges of digraphs in $\mathcal{D}(3,3)$ and $\mathcal{D}(4,4)$ with directed cuts

Abstract

For nonnegative integers $k$ and $l$, let $\mathcal{D}(k,l)$ denote the family of digraphs in which every vertex has either indegree at most $k$ or outdegree at most $l$. In this paper we prove that the edges of every digraph in $\mathcal{D}(3,3)$ and $\mathcal{D}(4,4)$ can be covered by at most five directed cuts and present an example in $\mathcal{D}(3,3)$ showing that this result is best possible.

Cited by in corpus (1)

• Degrees in oriented hypergraphs and Ramsey p-chromatic number