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.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1286,
author = {Marietjie Frick and Susan van Aardt and Gcina Dlamini and Jean Dunbar and Ortrud Oellermann},
title = {The directed path partition conjecture},
journal = {Discussiones Mathematicae Graph Theory},
volume = {25},
year = {2005},
pages = {331-343},
zbl = {1118.05040},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1286}
}
Marietjie Frick; Susan van Aardt; Gcina Dlamini; Jean Dunbar; Ortrud Oellermann. The directed path partition conjecture. Discussiones Mathematicae Graph Theory, Tome 25 (2005) pp. 331-343. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1286/
[000] [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.
[001] [2] J. Bang-Jensen, Digraphs: Theory, Algorithms and Applications (Springer-Verlag, London, 2002). | Zbl 1001.05002
[002] [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. | Zbl 0721.05027
[003] [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. | Zbl 0912.05048
[004] [5] M. Chudnovsky, N. Robertson, P.D. Seymour and R. Thomas, Progress on Perfect Graphs, Mathematical Programming Ser. B97 (2003) 405-422. | Zbl 1028.05035
[005] [6] J.E. Dunbar and M. Frick, Path kernels and partitions, JCMCC 31 (1999) 137-149. | Zbl 0941.05040
[006] [7] J.E. Dunbar and M. Frick, The Path Partition Conjecture is true for claw-free graphs, submitted. | Zbl 1121.05092
[007] [8] J.E. Dunbar, M. Frick and F. Bullock, Path partitions and maximal Pₙ-free sets, submitted. | Zbl 1056.05085
[008] [9] M. Frick and F. Bullock, Detour chromatic numbers of graphs, Discuss. Math. Graph Theory 21 (2001) 283-291, doi: 10.7151/dmgt.1150. | Zbl 1002.05021
[009] [10] M. Frick and I. Schiermeyer, An asymptotic result on the Path Partition Conjecture, submitted.
[010] [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.
[011] [12] F. Harary, R.Z. Norman and D. Cartwright, Structural Models (John Wiley and Sons, 1965). | Zbl 0139.41503
[012] [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.)
[013] [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).
[014] [15] M. Richardson, Solutions of irreflexive relations, Annals of Math. 58 (1953) 573-590, doi: 10.2307/1969755. | Zbl 0053.02902
[015] [16] B. Roy, Nombre chromatique et plus longs chemins d'un graphe, RAIRO, Série Rouge, 1 (1967) 127-132. | Zbl 0157.31302
[016] [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.
[017] [18] D.B. West, Introduction to Graph Theory (Prentice-Hall, Inc., London, second edition, 2001).