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

Abstract

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

How to cite

top

Marietjie 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. [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. [2] J. Bang-Jensen, Digraphs: Theory, Algorithms and Applications (Springer-Verlag, London, 2002). Zbl1001.05002
  3. [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. [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. [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. [6] J.E. Dunbar and M. Frick, Path kernels and partitions, JCMCC 31 (1999) 137-149. Zbl0941.05040
  7. [7] J.E. Dunbar and M. Frick, The Path Partition Conjecture is true for claw-free graphs, submitted. Zbl1121.05092
  8. [8] J.E. Dunbar, M. Frick and F. Bullock, Path partitions and maximal Pₙ-free sets, submitted. Zbl1056.05085
  9. [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. [10] M. Frick and I. Schiermeyer, An asymptotic result on the Path Partition Conjecture, submitted. 
  11. [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. [12] F. Harary, R.Z. Norman and D. Cartwright, Structural Models (John Wiley and Sons, 1965). Zbl0139.41503
  13. [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. [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. [15] M. Richardson, Solutions of irreflexive relations, Annals of Math. 58 (1953) 573-590, doi: 10.2307/1969755. Zbl0053.02902
  16. [16] B. Roy, Nombre chromatique et plus longs chemins d'un graphe, RAIRO, Série Rouge, 1 (1967) 127-132. Zbl0157.31302
  17. [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. [18] D.B. West, Introduction to Graph Theory (Prentice-Hall, Inc., London, second edition, 2001). 

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.