The directed path partition conjecture
Discussiones Mathematicae. Graph Theory, Tome 25 (2005) no. 3, pp. 331-343.

Voir la notice de l'article provenant de la source Library of Science

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
@article{DMGT_2005_25_3_a11,
     author = {Frick, Marietjie and van Aardt, Susan and Dlamini, Gcina and Dunbar, Jean and Oellermann, Ortrud},
     title = {The directed path partition conjecture},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {331--343},
     publisher = {mathdoc},
     volume = {25},
     number = {3},
     year = {2005},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2005_25_3_a11/}
}
TY  - JOUR
AU  - Frick, Marietjie
AU  - van Aardt, Susan
AU  - Dlamini, Gcina
AU  - Dunbar, Jean
AU  - Oellermann, Ortrud
TI  - The directed path partition conjecture
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2005
SP  - 331
EP  - 343
VL  - 25
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2005_25_3_a11/
LA  - en
ID  - DMGT_2005_25_3_a11
ER  - 
%0 Journal Article
%A Frick, Marietjie
%A van Aardt, Susan
%A Dlamini, Gcina
%A Dunbar, Jean
%A Oellermann, Ortrud
%T The directed path partition conjecture
%J Discussiones Mathematicae. Graph Theory
%D 2005
%P 331-343
%V 25
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2005_25_3_a11/
%G en
%F DMGT_2005_25_3_a11
Frick, Marietjie; van Aardt, Susan; Dlamini, Gcina; Dunbar, Jean; Oellermann, Ortrud. The directed path partition conjecture. Discussiones Mathematicae. Graph Theory, Tome 25 (2005) no. 3, pp. 331-343. http://geodesic.mathdoc.fr/item/DMGT_2005_25_3_a11/

[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 Pₙ-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).