DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

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

PDF

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

THE DIRECTED PATH PARTITION CONJECTURE

Marietjie Frick and Susan van Aardt

Department of Mathematical Sciences
University of South Africa
P.O. Box 392, Pretoria, 0001 South Africa
e-mail: frickm@unisa.ac.za
e-mail: vaardsa@unisa.ac.za

Gcina Dlamini

Department of Mathematics, University of Swaziland
Private Bag 4, Kwaluseni, M 201, Swaziland
e-mail: DLAMINIG@science.uniswa.sz

Jean Dunbar

Department of Mathematics, Computer Science and Physics
Converse College
Spartanburg, South Carolina 29302, USA
e-mail: Jean.Dunbar@converse.edu

Ortrud Oellermann

Department of Mathematics and Statistics
University of Winnipeg
Manitoba R3B 2E9 Canada
e-mail: o.oellermann@uwinnipeg.ca

Abstract

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.

References

[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