ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory


Discussiones Mathematicae Graph Theory 25(3) (2005) 331-343
DOI: 10.7151/dmgt.1286


Marietjie Frick and Susan van Aardt

Department of Mathematical Sciences
University of South Africa
P.O. Box 392, Pretoria, 0001 South Africa

Gcina Dlamini

Department of Mathematics, University of Swaziland
Private Bag 4, Kwaluseni, M 201, Swaziland

Jean Dunbar

Department of Mathematics, Computer Science and Physics
Converse College
Spartanburg, South Carolina 29302, USA

Ortrud Oellermann

Department of Mathematics and Statistics
University of Winnipeg
Manitoba R3B 2E9 Canada


The Directed Path Partition Conjecture is the following: If D is a digraph that contains no path with more than λ vertices then, for every pair (a,b) of positive integers with λ = 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.We develop methods for finding the desired partitions for various classes of digraphs.

Keywords: longest path, Path Partition Conjecture, vertex partition, digraph, prismatic colouring.

2000 Mathematics Subject Classification: 05C20, 05C38, 05C15.


[1] J.A. Bondy, Handbook of Combinatorics, eds. R.L. Graham, M. Grötschel and L. Lovász (The MIT Press, Cambridge, MA, 1995) Vol I, p. 49.
[2] J. Bang-Jensen, Digraphs: Theory, Algorithms and Applications (Springer-Verlag, London, 2002).
[3] C. Berge and P. Duchet, Recent problems and results about kernels in directed graphs, Discrete Math. 86 (1990) 27-31, doi: 10.1016/0012-365X(90)90346-J.
[4] I. Broere, M. Dorfling, J.E. Dunbar and M. Frick, A path(ological) partition problem, Discuss. Math. Graph Theory 18 (1998) 115-125, doi: 10.7151/dmgt.1068.
[5] M. Chudnovsky, N. Robertson, P.D. Seymour and R. Thomas, Progress on Perfect Graphs, Mathematical Programming Ser. B97 (2003) 405-422.
[6] J.E. Dunbar and M. Frick, Path kernels and partitions, JCMCC 31 (1999) 137-149.
[7] J.E. Dunbar and M. Frick, The Path Partition Conjecture is true for claw-free graphs, submitted.
[8] J.E. Dunbar, M. Frick and F. Bullock, Path partitions and maximal Pn-free sets, submitted.
[9] M. Frick and F. Bullock, Detour chromatic numbers of graphs, Discuss. Math. Graph Theory 21 (2001) 283-291, doi: 10.7151/dmgt.1150.
[10] M. Frick and I. Schiermeyer, An asymptotic result on the Path Partition Conjecture, submitted.
[11] T. Gallai, On directed paths and circuits, in: P. Erdös and G. Katona, eds., Theory of graphs (Academic press, New York, 1968) 115-118.
[12] F. Harary, R.Z. Norman and D. Cartwright, Structural Models (John Wiley and Sons, 1965).
[13] J.M. Laborde, C. Payan and N.H. Xuong, Independent sets and longest directed paths in digraphs, in: Graphs and other combinatorial topics (Prague,1982) 173-177 (Teubner-Texte Math., 59 1983.)
[14] L.S. Melnikov and I.V. Petrenko, On the path kernel partitions in undirected graphs, Diskretn. Anal. Issled. Oper. Series 1, 9 (2) (2002) 21-35 (Russian).
[15] M. Richardson, Solutions of irreflexive relations, Annals of Math. 58 (1953) 573-590, doi: 10.2307/1969755.
[16] B. Roy, Nombre chromatique et plus longs chemins d'un graphe, RAIRO, Série Rouge, 1 (1967) 127-132.
[17] L.M. Vitaver, Determination of minimal colouring of vertices of a graph by means of Boolean powers of the incidence matrix (Russian). Dokl. Akad. Nauk, SSSR 147 (1962) 758-759.
[18] D.B. West, Introduction to Graph Theory (Prentice-Hall, Inc., London, second edition, 2001).

Received 18 March 2004
Revised 28 October 2004