# The directed path partition conjecture

Marietjie Frick; Susan van Aardt; Gcina Dlamini; Jean Dunbar; Ortrud Oellermann

Discussiones Mathematicae Graph Theory (2005)

- Volume: 25, Issue: 3, page 331-343
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topMarietjie Frick, et al. "The directed path partition conjecture." Discussiones Mathematicae Graph Theory 25.3 (2005): 331-343. <http://eudml.org/doc/270639>.

@article{MarietjieFrick2005,

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.},

author = {Marietjie Frick, Susan van Aardt, Gcina Dlamini, Jean Dunbar, Ortrud Oellermann},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {longest path; Path Partition Conjecture; vertex partition; digraph; prismatic colouring; path partition conjecture},

language = {eng},

number = {3},

pages = {331-343},

title = {The directed path partition conjecture},

url = {http://eudml.org/doc/270639},

volume = {25},

year = {2005},

}

TY - JOUR

AU - Marietjie Frick

AU - Susan van Aardt

AU - Gcina Dlamini

AU - Jean Dunbar

AU - Ortrud Oellermann

TI - The directed path partition conjecture

JO - Discussiones Mathematicae Graph Theory

PY - 2005

VL - 25

IS - 3

SP - 331

EP - 343

AB - 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.

LA - eng

KW - longest path; Path Partition Conjecture; vertex partition; digraph; prismatic colouring; path partition conjecture

UR - http://eudml.org/doc/270639

ER -

## References

top- [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). Zbl1001.05002
- [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. Zbl0721.05027
- [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. Zbl0912.05048
- [5] M. Chudnovsky, N. Robertson, P.D. Seymour and R. Thomas, Progress on Perfect Graphs, Mathematical Programming Ser. B97 (2003) 405-422. Zbl1028.05035
- [6] J.E. Dunbar and M. Frick, Path kernels and partitions, JCMCC 31 (1999) 137-149. Zbl0941.05040
- [7] J.E. Dunbar and M. Frick, The Path Partition Conjecture is true for claw-free graphs, submitted. Zbl1121.05092
- [8] J.E. Dunbar, M. Frick and F. Bullock, Path partitions and maximal Pₙ-free sets, submitted. Zbl1056.05085
- [9] M. Frick and F. Bullock, Detour chromatic numbers of graphs, Discuss. Math. Graph Theory 21 (2001) 283-291, doi: 10.7151/dmgt.1150. Zbl1002.05021
- [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). Zbl0139.41503
- [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. Zbl0053.02902
- [16] B. Roy, Nombre chromatique et plus longs chemins d'un graphe, RAIRO, Série Rouge, 1 (1967) 127-132. Zbl0157.31302
- [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).

## Citations in EuDML Documents

top- Susan van Aardt, Marietjie Frick, Joy Singleton, Independent Detour Transversals in 3-Deficient Digraphs
- Hortensia Galeana-Sánchez, Ricardo Gómez, Juan José Montellano-Ballesteros, Independent transversals of longest paths in locally semicomplete and locally transitive digraphs
- Marietjie Frick, A Survey of the Path Partition Conjecture

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.