zbMATH — the first resource for mathematics

Large monotone paths in graphs with bounded degree. (English) Zbl 1010.05044
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)\).

05C38 Paths and cycles
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C35 Extremal problems in graph theory
Full Text: DOI