Path partitions and packs of acyclic digraphs

Ron Aharoni, Irith Ben-Arroyo Hartman and Alan Jerome Hoffman

Vol. 118 (1985), No. 2, 249–259

DOI: 10.2140/pjm.1985.118.249

Abstract

Let G be an acyclic directed graph with |V (G)|≥ k. We prove that there exists a colouring {C₁,C₂,…,C_m} such that for every collection {P₁,P₂,…,P_k} of k vertex disjoint paths with |⋃ _j=1^kP_j| a maximum, each colour class C_i meets min{|C_i|,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.

Mathematical Subject Classification 2000

Primary: 05C20

Secondary: 05C38

Milestones

Received: 6 June 1984

Published: 1 June 1985