Geodesic
A Survey of the Path Partition Conjecture
Discussiones Mathematicae. Graph Theory, Tome 33 (2013) no. 1, pp. 117-131.

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: Path Partition Conjecture, Path Kernel Conjecture, generalized colourings, additive hereditary properties 
@article{DMGT_2013_33_1_a9,
     author = {Frick, Marietjie},
     title = {A {Survey} of the {Path} {Partition} {Conjecture}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {117--131},
     publisher = {mathdoc},
     volume = {33},
     number = {1},
     year = {2013},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2013_33_1_a9/}
}
TY  - JOUR
AU  - Frick, Marietjie
TI  - A Survey of the Path Partition Conjecture
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2013
SP  - 117
EP  - 131
VL  - 33
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2013_33_1_a9/
LA  - en
ID  - DMGT_2013_33_1_a9
ER  - 
%0 Journal Article
%A Frick, Marietjie
%T A Survey of the Path Partition Conjecture
%J Discussiones Mathematicae. Graph Theory
%D 2013
%P 117-131
%V 33
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2013_33_1_a9/
%G en
%F DMGT_2013_33_1_a9
Frick, Marietjie. A Survey of the Path Partition Conjecture. Discussiones Mathematicae. Graph Theory, Tome 33 (2013) no. 1, pp. 117-131. http://geodesic.mathdoc.fr/item/DMGT_2013_33_1_a9/

[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

[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

[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

[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

[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

[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

[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

[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

[13] J.A. Bondy, Basic graph theory: Paths and circuits, in: Handbook of Combinatorics, R.L. Graham, M. Grötschel, and L. Lovász, (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

[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

[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

[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

[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

[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

[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

[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

[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

[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).

[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

[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ász, (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

[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

[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

[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

[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

[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ń (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

[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

[51] J. Vronka, Vertex sets of graphs with prescribed properties, Thesis supervised by P. Mihók, (P.J. ˇSafárik 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