Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4650945 | Discrete Mathematics | 2006 | 10 Pages |
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
Jørgen Bang-Jensen, Morten Hegner Nielsen, Anders Yeo,