Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2005 | 25 | 3 | 331-343
Tytuł artykułu

The directed path partition conjecture

Treść / Zawartość
Warianty tytułu
Języki publikacji
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.
Opis fizyczny
  • Department of Mathematical Sciences, University of South Africa, P.O. Box 392, Pretoria, 0001 South Africa
  • Department of Mathematical Sciences, University of South Africa, P.O. Box 392, Pretoria, 0001 South Africa
  • Department of Mathematics, University of Swaziland, Private Bag 4, Kwaluseni, M 201, Swaziland
  • Department of Mathematics, Computer Science and Physics, Converse College, Spartanburg, South Carolina 29302, USA
  • Department of Mathematics and Statistics, University of Winnipeg, Manitoba R3B 2E9 Canada
  • [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).
Typ dokumentu
Identyfikator YADDA
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.