Article in press
Authors:
Marietjie Frick
Department of Mathematical Sciences University of South Africa P.O. Box 392Pretoria 0001 SOUTH AFRICA
email: marietjie.frick@gmail.com
Title:
The Strong Path Partition Conjecture holds for a = 9
PDFSource:
Discussiones Mathematicae Graph Theory
Received: 2025-01-19 , Revised: 2025-05-23 , Accepted: 2025-05-23 , Available online: 2025-06-23 , https://doi.org/10.7151/dmgt.2590
Abstract:
The detour order of a graph $G$, denoted by $\tau (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 $\tau (\langle
A\rangle)\leq a$ and $\tau (\langle B\rangle)\leq b$, we say that $(A,B)$ is an
$(a,b)$-partition of $G$. If equality holds in both instances, i.e., if
$\tau (\langle A\rangle)= a$ and $\tau (\langle B\rangle)= b$, we call $(A,B)$
an exact $(a,b)$-partition. The Path Partition Conjecture asserts that
if $G$ is any graph and $a,b$ any pair of positive integers such that
$\tau (G)=a+b$, then $G$ has an $(a,b)$-partition. The Strong Path Partition
Conjecture asserts that, under the same conditions, $G$ has an exact $(a,b)$-partition.
The Path Partition Conjecture is now more than 40 years old. It first appeared
in the literature in a paper by Laborde, Payan and Xuong (1982). It is known
that the Path Partition Conjecture holds for all $a\leq 8$. The case $a\leq 5$
was first proved by Vronka (1986), the case $a=6$ by Dunbar and Frick (1999)
and the cases $a=7$ and $a=8$ by Melnikov and Petrenko (2002 and 2005). Using a
new partition strategy involving a recursive procedure, De Wet, Dunbar, Frick
and Oellermann (2024) improved these results by showing that the Strong Path
Partition Conjecture holds for $a\leq 8$. By expanding and refining the recursive
procedure, we prove that the Strong Partition Conjecture also holds for $a=9$.
Keywords:
Path Partition Conjecture, Strong Path Partition Conjecture, vertex partitions, path kernels, longest path
References:
- 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 - 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 - J.E. Dunbar, M. Frick and F. Bullock, Path Partitions and $P_n$-free sets, Discrete Math. 289 (2004) 145–155.
https://doi.org/10.1016/j.disc.2004.07.012 - J.P. de Wet, J.D. Dunbar, M. Frick and O.R. Oellermann, On the Strong Path Partition Conjecture, Discuss. Math. Graph Theory 44 (2024) 691–715.
https://doi.org/10.7151/dmgt.2468 - J.E. Dunbar and M. Frick, Path kernels and partitions, J. Combin. Math. Combin. Comput. 31 (1999) 137–149.
- 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 - J.E. Dunbar and M. Frick, The Path Partition Conjecture, in: Graph Theory: Favourite Conjectures and Open Problems - 2, R.Gera, T.W. Haynes and S. Hedetniemi (Ed(s)), (Springer Cham 2018) 101–113.
https://doi.org/10.1007/978-3-319-97686-0 - 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 - M. Frick and C. Whitehead, A new approach to the Path Partition Conjecture, Util. Math. 99 (2006) 195–206.
- A.N. Glebov and D.J. Zambalaeva, Path partitioning planar graphs, Sib. Èlectron. Mat. Izv. 4 (2007) 450–459, in Russian, English abstract.
- S. Hedetniemi, My top $10$ graph theory conjectures and open problems, in: Graph Theory: Favorite Conjectures and Open Problems - 1, R. Gera, S. Hedetniemi and C. Larson (Ed(s)), (Springer Cham 2016) 109–134.
https://doi.org/10.1007/978-3-319-31940-7_8 - W. He and B. Wang, A note on path kernels and partitions, Discrete Math. 310 (2010) 3040–3042.
https://doi.org/10.1016/j.disc.2010.06.029 - 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 - 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, (Teubner-Texte Math. 59 1983) 173–177.
- L.S. Melnikov and I.V. Petrenko, On path kernels and partitions in nondirected graphs, Diskretn. Anal. Issled. Oper. 9 (2002) 21–35, in Russian.
- 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 2005) 145–160, in Russian.
- J. Vronka, Vertex Sets of Graphs with Prescribed Properties, PhD Thesis (P.J. Safárik University, Košice, 1986).
Close