DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 33(1) (2013) 117-131
DOI: https://doi.org/10.7151/dmgt.1673

Dedicated to Mietek Borowiecki on the occasion of his 70th birthday

A survey of the Path Partition Conjecture

Marietjie Frick

Department of Mathematical Sciences
School of Science
University of South Africa

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.

Keywords: Path Partition Conjecture, Path Kernel Conjecture, generalized colourings, additive hereditary properties

2010 Mathematics Subject Classification: 05C15, 05C38, 05C70.

References

[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-Sánchez, 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-Mejía, 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'.
[48]P. Mihók, Problem 4, in: M. Borowiecki and Z. Skupień (Eds.), Graphs, Hypergraphs and Matroids, (Zielona Góra, 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. Šafárik University, Košice 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.

Received 1 December 2012
Accepted 7 January 2013

Close