Geodesic
On the Strong Path Partition Conjecture
Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 2, pp. 691-715

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

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},
     publisher = {mathdoc},
     volume = {44},
     number = {2},
     year = {2024},
     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
PB  - mathdoc
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
%I mathdoc
%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/