Advances in Aharoni-Hartman-Hoffman's Conjecture for Split digraphs

Let k be a positive integer and let D be a digraph. A (path) k-packPk of D is a collection of at most k vertex-disjoint paths in D. The weight of a k-pack Pk is the number of vertices covered by it and we say Pk is optimal if its weight is maximum. A vertex-coloring C is orthogonal to a k-pack Pk if each color class C∈C meets min⁡{|C|,k} paths of Pk. In 1985, Aharoni, Hartman and Hoffman conjectured that for any optimal k-pack of D there exists a coloring orthogonal to it. In this paper we give a partial answer to this question by presenting two special types of k-packs in split digraphs for which we can always find an orthogonal coloring.