Download PDF - The directed path partition conjectureAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

The directed path partition conjecture

Authors 1, 1, 2, 3, 4

Affiliations

  1. Department of Mathematical Sciences, University of South Africa, P.O. Box 392, Pretoria, 0001 South Africa
  2. Department of Mathematics, University of Swaziland, Private Bag 4, Kwaluseni, M 201, Swaziland
  3. Department of Mathematics, Computer Science and Physics, Converse College, Spartanburg, South Carolina 29302, USA
  4. Department of Mathematics and Statistics, University of Winnipeg, Manitoba R3B 2E9 Canada

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

ENG
longest path, Path Partition Conjecture, vertex partition, digraph, prismatic colouring

Bibliography

  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).
Discussiones Mathematicae Graph Theory
2005/25/3
Export to PBN, Opens in new tab
Pages:
331-343
Main language of publication
English
Received
2004-03-18
Accepted
2004-10-28
Published
2005

DOI: 10.7151/dmgt.1286

Exact and natural sciences