The Path Partition Conjecture and 3-(quasi-)Transitive Digraphs

Abstract

A digraph $D=(V,E)$ is 3-transitive (respectively, 3-quasi-transitive) if whenever $(u,v,w,z)$ is a directed path of length 3, $(u,z)\in E$ (respectively, $(u,z)\in E$ or $(z,u)\in E$). These digraphs extend the concepts of transitive and quasi-transitive digraphs, respectively. For 3-transitive and 3-quasi-transitive digraphs, only the strong case has been characterized. In this paper, we introduce the notion of semi-acyclic digraphs and use it to describe completely the structure of 3-transitive and 3-quasi-transitive digraphs. As an application of this type of structure description, we prove that the path partition conjecture holds for the class of extended semi-acyclic digraphs, which generalizes two previously known results on the conjecture.

arXiv comment27 pages, 2 figures