A Survey of the Path Partition Conjecture

Marietjie Frick

Discussiones Mathematicae Graph Theory (2013)

  • Volume: 33, Issue: 1, page 117-131
  • ISSN: 2083-5892

Abstract

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

How to cite

top

Marietjie Frick. "A Survey of the Path Partition Conjecture." Discussiones Mathematicae Graph Theory 33.1 (2013): 117-131. <http://eudml.org/doc/267737>.

@article{MarietjieFrick2013,
abstract = {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.},
author = {Marietjie Frick},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {Path Partition Conjecture; Path Kernel Conjecture; generalized colourings; additive hereditary properties; path partition conjecture; path kernel conjecture},
language = {eng},
number = {1},
pages = {117-131},
title = {A Survey of the Path Partition Conjecture},
url = {http://eudml.org/doc/267737},
volume = {33},
year = {2013},
}

TY - JOUR
AU - Marietjie Frick
TI - A Survey of the Path Partition Conjecture
JO - Discussiones Mathematicae Graph Theory
PY - 2013
VL - 33
IS - 1
SP - 117
EP - 131
AB - 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.
LA - eng
KW - Path Partition Conjecture; Path Kernel Conjecture; generalized colourings; additive hereditary properties; path partition conjecture; path kernel conjecture
UR - http://eudml.org/doc/267737
ER -

References

top
  1. [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. Zbl1266.05044
  2. [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] Zbl1118.05040
  3. [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] Zbl1195.05030
  4. [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] Zbl1234.05116
  5. [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. Zbl1178.05046
  6. [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. Zbl1242.05141
  7. [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] Zbl1066.05107
  8. [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] Zbl1256.05085
  9. [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] Zbl1103.05036
  10. [10] J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications, Second Edition (Springer-Verlag, London, 2009). Zbl1170.05002
  11. [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] Zbl1065.05055
  12. [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] Zbl0870.05026
  13. [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. Zbl0849.05044
  14. [14] O.V. Borodin, On decomposition of graphs into degenerate subgraphs, Diskret. Analiz. 28 (1976) 3-11. Zbl0425.05058
  15. [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] Zbl0902.05026
  16. [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. Zbl0946.05053
  17. [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] Zbl0912.05048
  18. [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] Zbl1030.05038
  19. [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 Zbl0902.05027
  20. [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] Zbl0906.05059
  21. [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. [22] F. Bullock and M. Frick, Detour chromatic numbers of graphs, Discuss. Math. Graph Theory 21 (2001) 283-291. doi:0.7151/dmgt.1150 Zbl1002.05021
  23. [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] Zbl0173.26204
  24. [24] A. Dudek and P. Wojda, Pm-saturated graphs with minimum size, Opuscula Math. 24 (2004) 43-55. Zbl1093.05508
  25. [25] J.E. Dunbar and M. Frick, Path kernels and partitions, J. Combin. Math. Combin. Comput. 31 (1999) 137-149. Zbl0941.05040
  26. [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] Zbl1121.05092
  27. [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. [28] M. Frick and P. Katrenič, Progress on the Traceability Conjecture for oriented graphs, Discrete Math. Theor. Comput. Sci. 10 (2008) 105-114. Zbl1196.05036
  29. [29] M. Frick and I. Schiermeyer, An asymptotic result on the path partition conjecture Electron. J. Combin. 12 (2005) #R48. 
  30. [30] M. Frick and C. Whitehead, A new approach to the Path Partition Conjecture, Util. Math. 99 (2006) 195-206. Zbl1114.05080
  31. [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] Zbl1193.05084
  32. [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. [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). Zbl1132.05315
  34. [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. [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). Zbl1170.05001
  36. [36] P. Hajnal, Graph Partitions, Thesis supervised by L. Lov´asz, (J.A. University, Szeged, 1984) (in Hungarian). 
  37. [37] F. Havet, Stable set meeting every longest path, Discrete Math. 289 (2004) 169-173. doi:10.1016/j.disc.2004.07.013[Crossref] Zbl1056.05072
  38. [38] T.R. Jensen and B. Toft, Graph Coloring Problems (Wiley-Interscience Publications, New York, 1995). Zbl0855.05054
  39. [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] Zbl1293.05296
  40. [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. [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] Zbl0593.05041
  42. [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. [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] Zbl0202.23502
  44. [44] L. Lovász, On decomposition of graphs, Studia Sci. Math. Hungar. 1 (1966) 237-238. Zbl0151.33401
  45. [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. [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. [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. [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. [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. [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. [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. [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] Zbl1223.05146

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.