Large monotone paths in graphs with bounded degree

We prove that for every > 0 and positive integer r, there exists ∆0 = ∆0() such that if ∆> ∆0 and n> n(∆, , r) then there exists a packing of Kn with b(n − 1)/∆c graphs, each having maximum degree at most ∆ and girth at least r, where at most n2 edges are unpacked. This result is used to prove the following: Let f be an assignment of real numbers to the edges of a graph G. Let α(G, f) denote the maximum length of a monotone simple path of G with respect to f. Let α(G) be the minimum of α(G, f), ranging over all possible assignments. Now let α ∆ be the maximum of α(G) ranging over all graphs with maximum degree at most ∆. We prove that ∆ + 1 ≥ α ∆ ≥ ∆(1 − o(1)). This extends some results of Graham and Kleitman [6] and of Calderbank, Chung and Sturtevant [4] who considered α(Kn).