2014/05/08 by Yair Caro, Caro, Yair, Josef Lauri +3
Mathematics · #05C07 05C38 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C07 #msc:05C38
paper · pdf · doi:10.48550/arxiv.1405.1812
arxiv created 2014/05/08 · arxiv updated 2014/05/09
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 investigate 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 inequalities. We conclude by indicating some open problems which our results point to.