Frick, Marietjie; van Aardt, Susan; Dlamini, Gcina; Dunbar, Jean; Oellermann, Ortrud The directed path partition conjecture. (English) Zbl 1118.05040 Discuss. Math., Graph Theory 25, No. 3, 331-343 (2005). The directed path partition conjecture says that every digraph is \(\lambda\)-partitionable which means that for every digraph \(D\) which contains no path with more than \(\lambda\) vertices and for every pair \((a,b)\) of positive integers with \(\lambda=a+b\) there exists a vertex partition \((A,B)\) of \(D\) such that no path in \(D[A]\) has more than \(a\) vertices and no path in \(D[B]\) has more than \(b\) vertices. In this paper the directed path partition conjecture is proved for various classes of digraphs. For example, if \(D\) contains a kernel in a certain induced subdigraph then \(D\) has a \((1,\lambda-1)\)-partition. It is also proved that acyclic digraphs, unicyclic digraphs and transitive digraphs are \(\lambda\)-partitionable. Reviewer: Arnfried Kemnitz (Braunschweig) Cited in 10 Documents MSC: 05C20 Directed graphs (digraphs), tournaments 05C38 Paths and cycles 05C15 Coloring of graphs and hypergraphs Keywords:longest path; path partition conjecture; vertex partition; digraph; prismatic colouring PDFBibTeX XMLCite \textit{M. Frick} et al., Discuss. Math., Graph Theory 25, No. 3, 331--343 (2005; Zbl 1118.05040) Full Text: DOI