Pełnotekstowe zasoby PLDML oraz innych baz dziedzinowych są już dostępne w nowej Bibliotece Nauki.
Zapraszamy na


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2013 | 33 | 1 | 117-131

Tytuł artykułu

A Survey of the Path Partition Conjecture


Treść / Zawartość

Warianty tytułu

Języki publikacji



The Path Partition Conjecture (PPC) states that if G is any graph and (λ1, λ2) any pair of positive integers such that G has no path with more than λ1 + λ2 vertices, then there exists a partition (V1, V2) of the vertex set of G such that Vi has no path with more than λi vertices, i = 1, 2. We present a brief history of the PPC, discuss its relation to other conjectures and survey results on the PPC that have appeared in the literature since its first formulation in 1981.









Opis fizyczny




  • Department of Mathematical Sciences School of Science University of South Africa


  • [1] S.A. van Aardt, A.P. Burger, J.E. Dunbar, M. Frick, J.M. Harris and J.E. Singleton, An iterative approach to the traceabiltiy conjecture for oriented graphs, submitted.
  • [2] S.A. van Aardt, G. Dlamini, J.E. Dunbar, M. Frick, and O.R. Oellermann, The directed path partition conjecture, Discuss. Math. Graph Theory 25 (2005) 331-343. doi:10.7151/dmgt.1286[Crossref]
  • [3] S.A. van Aardt, J.E. Dunbar, M. Frick, P. Katrenič, M.H. Nielsen, and O.R. Oellermann, Traceability of k-traceable oriented graphs, Discrete Math. 310 (2010) 1325-1333. doi:10.1016/j.disc.2009.12.022[Crossref]
  • [4] S.A. van Aardt, J.E. Dunbar, M. Frick and M.H. Nielsen, Cycles in k-traceable oriented graphs, Discrete Math. 311 (2011) 2085-2094. doi:10.1016/j.disc.2011.05.032[Crossref]
  • [5] S.A. van Aardt, J.E. Dunbar, M. Frick, M.H. Nielsen, and O.R. Oellermann, A traceability conjecture for oriented graphs, Electron. J. Combin. 15 (2008) #R150.
  • [6] S.A. van Aardt, M. Frick and C. Whitehead, Significant differences between path partitions in directed and undirected graphs, Util. Math. 83 (2010) 179-185.
  • [7] R.E.L. Aldred and C. Thomassen, Graphs with not all possible path-kernels, Discrete Math. 285 (2004) 297-300. doi:10.1016/j.disc.2004.02.012[Crossref]
  • [8] A. Arroyo and H. Galeana-Śanchez, The Path Partition Conjecture is true for some generalizations of tournaments, Discrete Math. 313 (2013) 293-300. doi:10.1016/j.disc.2012.10.014[Crossref]
  • [9] J. Bang-Jensen, M.H. Nielsen, and A. Yeo, Longest path partitions in generalizations of tournaments, Discrete Math. 306 (2006) 1830-1839. doi:10.1016/j.disc.2006.03.063[Crossref]
  • [10] J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications, Second Edition (Springer-Verlag, London, 2009).
  • [11] L.W. Beineke, J.E. Dunbar and M. Frick, Detour-saturated graphs, J. Graph Theory 49 (2005) 116-134. doi:10.1002/jgt.20069[Crossref]
  • [12] G. Benade, I. Broere, B. Jonck and M. Frick, Uniquely (m, k)τ -colourable graphs and k-τ -saturated graphs, Discrete Math. 162 (1996) 13-22. doi:10.1016/0012-365X(95)00301-C[Crossref]
  • [13] J.A. Bondy, Basic graph theory: Paths and circuits, in: Handbook of Combinatorics, R.L. Graham, M. Gr¨otschel, and L. Lov´asz, (Eds.), (The MIT Press, Cambridge, MA 1995) Vol I.
  • [14] O.V. Borodin, On decomposition of graphs into degenerate subgraphs, Diskret. Analiz. 28 (1976) 3-11.
  • [15] M. Borowiecki, I. Broere, M. Frick, P. Mihók, G. Semanišin, A survey of hereditary properties of graphs, Discuss. Math. Graph Theory, 17 (1997) 5-50. doi:10.7151/dmgt.1037[Crossref]
  • [16] S. Brandt, O. Favaron and Z. Ryjáček, Closure and stable hamiltonian properties in claw-free graphs, J. Graph Theory 349 (2000) 31-41.
  • [17] I. Broere, M. Dorfling, J.E. Dunbar and M. Frick, A Path(ological) Partition Problem, Discuss. Math. Graph Theory 18 (1998) 113-125. doi:10.7151/dmgt.1068[Crossref]
  • [18] I. Broere, S. Dorfling and E. Jonck, Generalized chromatic numbers and additive hereditary properties of graphs, Discuss. Math. Graph Theory 22 (2002) 259-270. doi:10.7151/dmgt.1174[Crossref]
  • [19] I. Broere, M. Frick and G. Semanišin, Maximal graphs with respect to hereditary properties, Discuss. Math. Graph Theory 17 (1997) 51-66. doi:0.7151/dmgt.1038
  • [20] I. Broere, P. Hajnal and P. Mihók, Partition problems and kernels of graphs, Discuss. Math. Graph Theory 17 (1997) 311-313 doi:10.7151/dmgt.1058[Crossref]
  • [21] F. Bullock, J.E. Dunbar and M. Frick, Path partitions and Pn-free sets, Discrete Math. 289 (2004) 145-155. doi:10.1016/j.disc.2004.07.012[Crossref]
  • [22] F. Bullock and M. Frick, Detour chromatic numbers of graphs, Discuss. Math. Graph Theory 21 (2001) 283-291. doi:0.7151/dmgt.1150
  • [23] G. Chartrand, D.P. Geller and S. Hedetniemi, A generalization of the chromatic number, Math. Proc. Cambridge Philos. Soc. 64 (1968) 265-271. doi:10.1017/S0305004100042808[Crossref]
  • [24] A. Dudek and P. Wojda, Pm-saturated graphs with minimum size, Opuscula Math. 24 (2004) 43-55.
  • [25] J.E. Dunbar and M. Frick, Path kernels and partitions, J. Combin. Math. Combin. Comput. 31 (1999) 137-149.
  • [26] J.E. Dunbar and M. Frick, The path partition conjecture is true for claw-free graphs, Discrete Math. 307 (2007) 1285-1290. doi:10.1016/j.disc.2005.11.065[Crossref]
  • [27] M. Frick, A survey on (m, k)-colorings, in: Quo Vadis, Graph Theory?, J.Gimbel, J.W. Kennedy and L.V. Quintas (Eds.), Annals Discrete Math. 55 (1993) 45-48.
  • [28] M. Frick and P. Katrenič, Progress on the Traceability Conjecture for oriented graphs, Discrete Math. Theor. Comput. Sci. 10 (2008) 105-114.
  • [29] M. Frick and I. Schiermeyer, An asymptotic result on the path partition conjecture Electron. J. Combin. 12 (2005) #R48.
  • [30] M. Frick and C. Whitehead, A new approach to the Path Partition Conjecture, Util. Math. 99 (2006) 195-206.
  • [31] H. Galeana-Sánchez, R. Gómez and J.J. Montellano-Ballesteros, Independent transversals of longest paths in locally semicomplete and locally transitive digraphs, Discuss. Math. Graph Theory 29 (2009) 469-480. doi:10.7151/dmgt.1458[Crossref]
  • [32] H. Galeana-Sánchez, H.A. Rincón-Meja, Independent sets which meet all longest paths, Discrete Math. 152 (1996) 141-145. doi:10.1016/0012-365X(94)00261-G[Crossref]
  • [33] A.N. Glebov and D.J. Zambalaeva, Path partitioning planar graphs, Siberian Electron. Math. Reports ( 4 (2007) 450-459 (in Russian, English abstract).
  • [34] W. He and B. Wang, A note on path kernels and partitions, Discrete Math. 310 (2010) 3040-3042. doi:10.1016/j.disc.2010.06.029[Crossref]
  • [35] J.M. Harris, J.L. Hirst and M.J. Mossinghoff, Combinatorics and Graph Theory (Second Edition) (Springer Science+Business Media, LLC, New York, 2008).
  • [36] P. Hajnal, Graph Partitions, Thesis supervised by L. Lov´asz, (J.A. University, Szeged, 1984) (in Hungarian).
  • [37] F. Havet, Stable set meeting every longest path, Discrete Math. 289 (2004) 169-173. doi:10.1016/j.disc.2004.07.013[Crossref]
  • [38] T.R. Jensen and B. Toft, Graph Coloring Problems (Wiley-Interscience Publications, New York, 1995).
  • [39] P. Katrenič and G. Semanišin,On a tree-partition problem, Electron. Notes Discrete Math. 28 (2007) 325-330. doi:10.1016/j.endm.2007.01.046[Crossref]
  • [40] P. Katrenič and G. Semanišin, A note on the Path Kernel Conjecture, Discrete Math. 309 (2009) 2551-2554. doi:10.1016/j.disc.2008.05.002[Crossref]
  • [41] L. Kászonyi and Zs. Tuza, Saturated graphs with minimal number of edges, J. Graph Theory 10 (1986) 203-210. doi:10.1002/jgt.3190100209[Crossref]
  • [42] 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)).
  • [43] D.R. Lick and A.T. White, k-degenerate graphs, Canad. J. Math. 22 (1970) 1082-1096. doi:10.4153/CJM-1970-125-1[Crossref]
  • [44] L. Lovász, On decomposition of graphs, Studia Sci. Math. Hungar. 1 (1966) 237-238.
  • [45] L.S. Mel’nikov and I.V. Petrenko, On path kernels and partitions of undirected graphs, Diskretn. Anal. Issled. Oper. 9 (2002) 21-35 (in Russian).
  • [46] L.S. Mel’nikov and I.V. Petrenko, Path kernels and cycle length in undirected graphs, in: V.N. Kassyanov (Ed.), Modern Problems of Program Construction, (ISI SB Russiam Academy of Science, Novosibirsk, 2002) 222-231 (in Russian).
  • [47] L.S. Mel’nikov and I.V. Petrenko, Path kernels and partitions of graphs with small cycle length, In: Methods and Tools of Program Construction and Optimization, V.N. Kasyanov (Ed.), (ISI SB Russian Academy of Science, Novosibirsk, 2005) 145-160 (in Russian).
  • [48] P.Mihók, Problem 4, in: M. Borowiecki and Z. Skupie´n (Eds.), Graphs, Hypergraphs and Matroids, (Zielona G´ora, 1985) p. 86.
  • [49] M.H. Nielsen, On a cycle partition problem, Discrete Math. 308 (2008) 6339-6347. doi:10.1016/j.disc.2007.12.002[Crossref]
  • [50] Z. Ryjáček, On a closure concept in claw-free graphs, J. Combin. Theory (B) 70 (1997) 217-224. doi:10.1006/jctb.1996.1732[Crossref]
  • [51] J. Vronka, Vertex sets of graphs with prescribed properties, Thesis supervised by P. Mihók, (P.J. ˇSaf´arik University, Koˇsice 1986), (in Slovak).
  • [52] F. Yang and E. Vumar, A note on a cycle partition problem, Appl. Math. Lett. 24 (2011) 1181-1184. doi:10.1016/j.aml.2011.02.003[Crossref]

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