Berge's conjecture on directed path partitions—a survey

AbstractBerge's conjecture from 1982 on path partitions in directed graphs generalizes and extends Dilworth's theorem and the Greene–Kleitman theorem which are well known for partially ordered sets. The conjecture relates path partitions to a collection of k independent sets, for each k⩾1. The conjecture is still open and intriguing for all k>1.11Only recently it was proved Berger and Ben-Arroyo Hartman [56] for k=2 (added in proof). In this paper, we will survey partial results on the conjecture, look into different proof techniques for these results, and relate the conjecture to other theorems, conjectures and open problems of Berge and other mathematicians