# 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)$$.

##### 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
Full Text: