Degree Monotone Paths

We shall study degree-monotone paths in graphs, a problem inspired by the celebrated theorem of Erdős-Szekeres concerning the longest monotone subsequence of a given sequence of numbers. A path P in a graph G is said to be a degree monotone path if the sequence of degrees of the vertices in P in the order they appear in P is monotonic. In this paper we shall consider these three problem related to this parameter: 1. Find bounds on mp(G) in terms of other parameters of G. 2. Study f(n, k) defined to be the maximum number of edges in a graph on n vertices with mp(G) < k. 3. Estimate the minimum and the maximum over all graph G on n vertices of mp(G) +mp(G). For the first problem our main tool will be the Gallai-Roy Theorem on directed paths and chromatic number. We shall also consider in some detail maximal planar and maximal outerplanar graphs in order to inves-tigate the sharpness of the bounds obtained. For the second problem we establish a close link between f(n, k) and the classical Turan numbers. For the third problem we establish some Nordhaus-Gaddum type of inequal-ities. We conclude by indicating some open problems which our results point to.