On the path partition of graphs

Let G be a graph of order n. The maximum and minimum degree of G are denoted by Δ and δ, respectively. The path partition number μ(G) of a graph G is the minimum number of paths needed to partition the vertices of G. Magnant, Wang and Yuan conjectured that [formula]. In this work, we give a positive answer to this conjecture, for Δ ≥ 2δ.

---

Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2022-2023)