×

Significant differences between path partitions in directed and undirected graphs. (English) Zbl 1242.05141

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.

MSC:

05C38 Paths and cycles
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C20 Directed graphs (digraphs), tournaments

Citations:

Zbl 1114.05080
PDFBibTeX XMLCite