On Greene-Kleitman's theorem for general digraphs

Abstract

Linial conjectured that Greene-Kleitman's theorem can be extended to general digraphs. We prove a stronger conjecture of Berge for digraphs having k-optimal path partitions consisting of 'long' paths. The same method yields known results for acyclic digraphs, and extensions of various theorems of Greene and Frank to acyclic digraphs. © 1993.