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.
@article{bwmeta1.element.doi-10_7151_dmgt_1673,
author = {Marietjie Frick},
title = {A Survey of the Path Partition Conjecture},
journal = {Discussiones Mathematicae Graph Theory},
volume = {33},
year = {2013},
pages = {117-131},
zbl = {1291.05062},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1673}
}
Marietjie Frick. A Survey of the Path Partition Conjecture. Discussiones Mathematicae Graph Theory, Tome 33 (2013) pp. 117-131. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1673/
[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. | Zbl 1266.05044
[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] | Zbl 1118.05040
[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] | Zbl 1195.05030
[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] | Zbl 1234.05116
[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. | Zbl 1178.05046
[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. | Zbl 1242.05141
[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] | Zbl 1066.05107
[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] | Zbl 1256.05085
[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] | Zbl 1103.05036
[10] J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications, Second Edition (Springer-Verlag, London, 2009). | Zbl 1170.05002
[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] | Zbl 1065.05055
[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] | Zbl 0870.05026
[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. | Zbl 0849.05044
[14] O.V. Borodin, On decomposition of graphs into degenerate subgraphs, Diskret. Analiz. 28 (1976) 3-11. | Zbl 0425.05058
[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] | Zbl 0902.05026
[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. | Zbl 0946.05053
[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] | Zbl 0912.05048
[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] | Zbl 1030.05038
[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 | Zbl 0902.05027
[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] | Zbl 0906.05059
[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 | Zbl 1002.05021
[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] | Zbl 0173.26204
[24] A. Dudek and P. Wojda, Pm-saturated graphs with minimum size, Opuscula Math. 24 (2004) 43-55. | Zbl 1093.05508
[25] J.E. Dunbar and M. Frick, Path kernels and partitions, J. Combin. Math. Combin. Comput. 31 (1999) 137-149. | Zbl 0941.05040
[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] | Zbl 1121.05092
[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. | Zbl 1196.05036
[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. | Zbl 1114.05080
[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] | Zbl 1193.05084
[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 (http://semr.math.nsc.ru) 4 (2007) 450-459 (in Russian, English abstract). | Zbl 1132.05315
[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). | Zbl 1170.05001
[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] | Zbl 1056.05072
[38] T.R. Jensen and B. Toft, Graph Coloring Problems (Wiley-Interscience Publications, New York, 1995). | Zbl 0855.05054
[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] | Zbl 1293.05296
[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] | Zbl 0593.05041
[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] | Zbl 0202.23502
[44] L. Lovász, On decomposition of graphs, Studia Sci. Math. Hungar. 1 (1966) 237-238. | Zbl 0151.33401
[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] | Zbl 1223.05146