DMGT

Article in volume

Authors:

J.P. de Wet

Johan Pieter de Wet

University of Pretoria

email: dwetjp@gmail.com

0000-0001-5124-5460

J.E. Dunbar

Jean E. Dunbar

Department of Mathematics, Computer Science and PhysicsConverse CollegeSpartanburg South Carolina 29302USA

email: jean.dunbar@converse.edu

M. Frick

Marietjie Frick

Department of Mathematical Sciences University of South Africa P.O. Box 392Pretoria 0001 SOUTH AFRICA

email: marietjie.frick@gmail.com

0000-0002-5011-604X

O.R. Oellermann

Ortrud R. Oellermann

Department of Mathematics and StatisticsUniversity of WinnipegManitoba R3B 2E9CANADA

email: o.oellermann@uwinnipeg.ca

0000-0003-3520-7514

Title:

On the Strong Path Partition Conjecture

PDF

Source:

Discussiones Mathematicae Graph Theory 44(2) (2024) 691-715

Received: 2021-09-13 , Revised: 2022-07-07 , Accepted: 2022-07-07 , Available online: 2022-08-29 , https://doi.org/10.7151/dmgt.2468

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) \le a$ and $\tau(\langle B \rangle) \le 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 $\tau (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\leq 8$.

Keywords:

Strong Path Partition Conjecture, 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
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.
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
F. Bullock, J.E. Dunbar and M. Frick, Path partitions and $P_n$-free sets, Discrete Math. 489 (2004) 145–155.
https://doi.org/10.1016/j.disc.2004.07.012
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, R. Gera, T.W. Haynes and S. Hedetniemi (Ed(s)), (Springer 2018).
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.
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, Graphs and Other Combinatorial Topics, Teubner-Texte Math. Prague (1982) 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.
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.
J. Vronka, Vertex Sets of Graphs with Prescribed Properties, PhD Thesis (P.J. Safárik University, Košice, 1986).