Communicated b-v the Managing Editors

decomposition of finite posets was extended by Greene and Kleitman (J. Combin. Theory Ser. A 20 (1976), 41-68). Using the Gallai-Milgram theorem (Acta Sci. Math. 2 1 (1960), 18 l-186) we prove a theorem on acyclic digraphs which contains the Greene-Kleitman theorem. The method of proof is derived from M. Saks’ elegant proof (Adv. in Math. 33 (1979), 207-211) of the Greene-Kleitman theorem. All our graph theoretical terminology is standard. A path in a directed graph is always a directed simple path. For a path P in a digraph G = (V, E) we let 1 PI denote the number of vertices in P. We let d, = d,(G) be the largest order of a k-colourable subgraph of G. A cover of G is a set A= w,,..., Mt) of disjoint paths which cover V, i.e., Y is the disjoint union U:=, V(M,). We define Bdm = 1 mink IMil)v i = 1 and ek = e,(G) = min I?,&&), the minimum being taken over all covers L The result of this note is that for acyclic digraphs