×

The directed path partition conjecture. (English) Zbl 1118.05040

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.

MSC:

05C20 Directed graphs (digraphs), tournaments
05C38 Paths and cycles
05C15 Coloring of graphs and hypergraphs
PDFBibTeX XMLCite
Full Text: DOI