International Journal of Mathematics and Mathematical Sciences
Volume 10 (1987), Issue 2, Pages 315-320

A monotone path in an edge-ordered graph

A. Bialostocki1 and Y. Roditty2

1Department of Mathematics and Applied Statistics, University of Idaho, Moscow 83843, Idaho, USA
2School of Mathematical Sciences, Tel-Aviv University, Tel-Aviv 69978, Israel

Received 8 January 1986; Revised 23 September 1986

Copyright © 1987 A. Bialostocki and Y. Roditty. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.


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:v1v2vk+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,,k1.

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.