Path partitions and packs of acyclic digraphs (Q1061135): Difference between revisions

The authors raise the following conjecture: Let G be a directed graph and let k be a positive integer. Then for every family \(\{P_ 1,P_ 2,...,P_ t\}\) of at most k disjoint paths for which \(| \cup^{t}_{i=1}V(P_ i)|\) is as large as possible, there exists a coloring \(\{C_ 1,C_ 2,...,C_ m\}\) such that every color class \(C_ i\) meets \(\min \{| C_ i|,k\}\) different paths of \(\{P_ i\}\). They prove that the conjecture holds for any acyclic digraph. The above mentioned conjecture is, in a sense, dual to a conjecture by Berge.