Article ID Journal Published Year Pages File Type
4650945 Discrete Mathematics 2006 10 Pages PDF
Abstract

We consider the so-called Path Partition Conjecture for digraphs which states that for every digraph, D  , and every choice of positive integers, λ1,λ2λ1,λ2, such that λ1+λ2λ1+λ2 equals the order of a longest directed path in D, there exists a partition of D   into two digraphs, D1D1 and D2D2, such that the order of a longest path in DiDi is at most λiλi, for i=1,2i=1,2.We prove that certain classes of digraphs, which are generalizations of tournaments, satisfy the Path Partition Conjecture and that some of the classes even satisfy the conjecture with equality.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , ,