Geodesic
On the Strong Path Partition Conjecture
Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 2, pp. 691-715 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

The detour order of a graph G, denoted by τ (G), is the order of a longest path in G. If a and b are positive integers and the vertex set of G can be partitioned into two subsets A and B such that τ(〈 A 〉) ≤ a and τ(〈 B 〉) ≤ b, we say that (A,B) is an (a,b)-partition of G. If equality holds in both instances, we call (A,B) an exact (a,b)-partition. The Path Partition Conjecture (PPC) asserts that if G is any graph and a,b any pair of positive integers such that τ (G)=a+b, then G has an (a,b)-partition. The Strong PPC asserts that under the same circumstances G has an exact (a,b)-partition. While a substantial body of work in support of the PPC has been developed over the past three decades, no results on the Strong PPC have yet appeared in the literature. In this paper we prove that the Strong PPC holds for a≤ 8.
Keywords: Strong Path Partition Conjecture, longest path 
@article{DMGT_2024_44_2_a13,
     author = {de Wet, Johan P. and Dunbar, Jean E. and Frick, Marietjie and Oellermann, Ortrud R.},
     title = {On the {Strong} {Path} {Partition} {Conjecture}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {691--715},
     year = {2024},
     volume = {44},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2024_44_2_a13/}
}
TY  - JOUR
AU  - de Wet, Johan P.
AU  - Dunbar, Jean E.
AU  - Frick, Marietjie
AU  - Oellermann, Ortrud R.
TI  - On the Strong Path Partition Conjecture
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2024
SP  - 691
EP  - 715
VL  - 44
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DMGT_2024_44_2_a13/
LA  - en
ID  - DMGT_2024_44_2_a13
ER  - 
%0 Journal Article
%A de Wet, Johan P.
%A Dunbar, Jean E.
%A Frick, Marietjie
%A Oellermann, Ortrud R.
%T On the Strong Path Partition Conjecture
%J Discussiones Mathematicae. Graph Theory
%D 2024
%P 691-715
%V 44
%N 2
%U http://geodesic.mathdoc.fr/item/DMGT_2024_44_2_a13/
%G en
%F DMGT_2024_44_2_a13
de Wet, Johan P.; Dunbar, Jean E.; Frick, Marietjie; Oellermann, Ortrud R. On the Strong Path Partition Conjecture. Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 2, pp. 691-715. http://geodesic.mathdoc.fr/item/DMGT_2024_44_2_a13/

[1] R.E.L. Aldred and C. Thomassen, Graphs with not all possible path-kernels, Discrete Math. 285 (2004) 297–300. https://doi.org/10.1016/j.disc.2004.02.012

[2] J.A. Bondy, Handbook of Combinatorics}, Eds. R.L. Graham, M. Grötschel and L. Lovász, The MIT Press, Cambridge, MA I (1995) 49.

[3] I. Broere, P. Hajnal, and P. Mihók, Partition problems and kernels of graphs, Discuss. Math. Graph Theory 17 (1997) 311–313. https://doi.org/10.7151/dmgt.1058

[4] F. Bullock, J.E. Dunbar and M. Frick, Path partitions and Pn-free sets, Discrete Math. 489 (2004) 145–155. https://doi.org/10.1016/j.disc.2004.07.012

[5] J.E. Dunbar and M. Frick, Path kernels and partitions, J. Combin. Math. Combin. Comput. 31 (1999) 137–149.

[6] J.E. Dunbar and M. Frick, The Path Partition Conjecture is true for claw-free graphs, Discrete Math. 307 (2007) 1285–1290. https://doi.org/10.1016/j.disc.2005.11.065

[7] J.E. Dunbar and M. Frick, The Path Partition Conjecture, in: Graph Theory: Favourite Conjectures and Open Problems, R. Gera, T.W. Haynes and S. Hedetniemi (Ed(s)), (Springer 2018).

[8] M. Frick and I. Schiermeyer, An asymptotic result on the path partition conjecture, Electron. J. Combin. 12 (2005) #R48. https://doi.org/10.37236/1945

[9] M. Frick and C. Whitehead, A new approach to the Path Partition Conjecture, Util. Math. 99 (2006) 195–206.

[10] P. Katrenič and G. Semanišin, A note on the Path Kernel Conjecture, Discrete Math. 309 (2009) 2551–2554. https://doi.org/10.1016/j.disc.2008.05.002

[11] J.M. Laborde, C. Payan and N.H. Xuong, Independent sets and longest directed paths in digraphs, Graphs and Other Combinatorial Topics, Teubner-Texte Math. Prague (1982) 59 (1983) 173–177.

[12] L.S. Melnikov and I.V. Petrenko, On path kernels and partitions in nondirected graphs, Diskretn. Anal. Issled. Oper. 9 (2002) 21–35.

[13] L.S. Melnikov 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(s)), (ISI SB Russian Academy of Science, Novosibirsk 200) 145–160.

[14] J. Vronka, Vertex Sets of Graphs with Prescribed Properties}, PhD Thesis (P.J. Safárik University, Košice, 1986).