Whitehead, Carol; Frick, Marietjie; van Aardt, Susan Significant differences between path partitions in directed and undirected graphs. (English) Zbl 1242.05141 Util. Math. 83, 179-185 (2010). Summary: If \(G\) is a graph or a digraph, the order of a longest path in \(G\) is denoted by \(\lambda(G)\), and the difference between the order of \(G\) and \(\lambda(G)\) is called the deficiency of \(G\). A vertex partition \((A, B)\) of a digraph \(G\) is called an \((a, b)\)-partition of \(G\) if \(\lambda(\langle A\rangle)\leq a\) and \(\lambda(\langle B\rangle)\leq b\). The Path Partition Conjecture (PPC) is the following: If \(G\) is a digraph and \((a, b)\) any pair of positive integers such that \(a+ b= \lambda(G)\), then \(G\) has an \((a, b)\)-partition. The PPC for graphs and the PPC for oriented graphs may be regarded as special cases of the PPC for digraphs. For connected graphs with deficiency 1 or 2, we actually have a stronger result than that conjectured by the PPC, in that even the condition \(a+ b= \lambda(G)- 1\) guarantees that \(G\) has an \((a, b)\)-partition [M. Frick and C. Whitehead, Util. Math. 69, 195–206 (2006; Zbl 1114.05080)]. However, we show in this note that the PPC for unilaterally connected oriented graphs of deficiency 1 or 2, if true, would be a best possible result. Cited in 2 Documents MSC: 05C38 Paths and cycles 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) 05C20 Directed graphs (digraphs), tournaments Keywords:longest path; deficiency Citations:Zbl 1114.05080 PDFBibTeX XMLCite \textit{C. Whitehead} et al., Util. Math. 83, 179--185 (2010; Zbl 1242.05141)