Significant differences between path partitions in directed and undirected graphs

Abstract

If G is a graph or a digraph, the order of a longest path in G is denoted by A(G), and the difference between the order of G and A(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 λ((A)) ≤ a and X((B)) ≤ 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 = A(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 = λ(G) - 1 guarantees that G has an (a, b)-partition (Prick and Whitehead, Utilitas Math. 99 (2006) 195-206). 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.