@Article{Kouider2023,
author = "Kouider, Mekkia and Zamime, Mohamed",
title = "On the path partition of graphs",
journal = "Opuscula Math.",
year = "2023",
volume = "43",
number = "6",
pages = "829--839",
doi = "https://doi.org/10.7494/OpMath.2023.43.6.829",
url = "https://doi.org/10.7494/OpMath.2023.43.6.829",
abstract = "Let \(G\) be a graph of order \(n\). The maximum and minimum degree of \(G\) are denoted by \(\Delta\) and \(\delta\), respectively. The path partition number \(\mu(G)\) of a graph \(G\) is the minimum number of paths needed to partition the vertices of \(G\). Magnant, Wang and Yuan conjectured that \[\mu(G)\leq\max \left\{\frac{n}{\delta+1},\frac{(\Delta-\delta)n}{\Delta+\delta}\right\}.\] In this work, we give a positive answer to this conjecture, for \(\Delta\geq 2\delta\).",
keywords = "path, partition",
issn = "1232-9274"
}