Article ID Journal Published Year Pages File Type
4647617 Discrete Mathematics 2013 8 Pages PDF
Abstract

The Path Partition Conjecture for digraphs states that for every digraph DD, 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 DD, there exists a partition of DD in two subdigraphs D1,D2D1,D2 such that the order of the longest path in DiDi is at most λiλi for i=1,2i=1,2.We present sufficient conditions for a digraph to satisfy the Path Partition Conjecture. Using these results, we prove that strong path mergeable, arc-locally semicomplete, strong 3-quasi-transitive, strong arc-locally in-semicomplete and strong arc-locally out-semicomplete digraphs satisfy the Path Partition Conjecture. Some previous results are generalized.

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