International Journal of Mathematics and Mathematical Sciences
Volume 10 (1987), Issue 2, Pages 315-320
A monotone path in an edge-ordered graph
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 , where is a graph and is a bijective function, . A monotone path of length in is a simple path in such that either or for .
It is proved that a graph has the property that contains a monotone path of length three for every iff contains as a subgraph, an odd cycle of length at least five or one of six listed graphs.