International Journal of Mathematics and Mathematical Sciences
Volume 10 (1987), Issue 2, Pages 315-320
doi:10.1155/S0161171287000383

A monotone path in an edge-ordered graph

Abstract

An edge-ordered graph is an ordered pair (G,f), where G is a graph and f is a bijective function, f:E(G)→{1,2,…,|E(G)|}. A monotone path of length k in (G,f) is a simple path Pk+1:v1v2…vk+1 in G such that either f({vi,vi+1})<f({vi+1,vi+2}) or f({vi,vi+1})>f({vi+1,vi}) for i=1,2,…,k−1.It is proved that a graph G has the property that (G,f) contains a monotone path of length three for every f iff G contains as a subgraph, an odd cycle of length at least five or one of six listed graphs.