Yuster, Raphael Large monotone paths in graphs with bounded degree. (English) Zbl 1010.05044 Graphs Comb. 17, No. 3, 579-587 (2001). Summary: We prove that for every \(\varepsilon> 0\) and positive integer \(r\), there exists \(\Delta_0= \Delta_0(\varepsilon)\) such that if \(\Delta> \Delta_0\) and \(n> n(\Delta,\varepsilon, r)\) then there exists a packing of \(K_n\) with \(\lfloor (n-1)/\Delta\rfloor\) graphs, each having maximum degree at most \(\Delta\) and girth at least \(r\), where at most \(\varepsilon n^2\) 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 \(\alpha(G,f)\) denote the maximum length of a monotone simple path of \(G\) with respect to \(f\). Let \(\alpha(G)\) be the minimum of \(\alpha(G, f)\), ranging over all possible assignments. Now let \(\alpha_\Delta\) be the maximum of \(\alpha(G)\) ranging over all graphs with maximum degree at most \(\Delta\). We prove that \(\Delta+ 1\geq\alpha_\Delta\geq \Delta(1- o(1))\). This extends some results of R. L. Graham and D. J. Kleitman [Period. Math. Hung. 3, 141-148 (1973; Zbl 0243.05116)] and of A. R. Calderbank et al. [Discrete Math. 50, 15-28 (1984; Zbl 0542.05058)] who considered \(\alpha(K_n)\). Cited in 10 Documents MSC: 05C38 Paths and cycles 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) 05C35 Extremal problems in graph theory Keywords:packing; monotone simple path Citations:Zbl 0243.05116; Zbl 0542.05058 PDFBibTeX XMLCite \textit{R. Yuster}, Graphs Comb. 17, No. 3, 579--587 (2001; Zbl 1010.05044) Full Text: DOI