Path partitions and packs of acyclic digraphs

Abstract

Let G be an acyclic directed graph with |V(G)| ≥ k. We prove that there exists a colouring {C1, C2, …, Cm} such that for every collection {P1, P2, …, Pk} of k vertex disjoint paths with |Uj=1k Pj| a maximum, each colour class Ci, meets min{|Cl|, k} of these paths. An analogous theorem, partially interchanging the roles of paths and colour classes, has been shown by Cameron [4] and Saks [17] and we indicate a third proof. © 1985 by Pacific Journal of Mathematics.