A monotone path in an edge-ordered graph
An edge-ordered graph is an ordered pair (G,f), where G is a graph and f is a bijective function, f: E(G)\(\to \{1,2,...,| E(G)| \}\). A monotone path of length k in (G,f) is a simple path \(P_{k+1}:\) \(v_ 1v_ 2...v_{k+1}\) in G such that either \(f(\{v_ i,v_{i+1}\})<f(\{v_{i+1},v_{i+2}\})\) or \(f(\{v_ i,v_{+1}\})>f(\{v_{i+1},v_ i\})\) 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.
- Altitude of regular graphs with girth at least five
- Monotone paths in edge-ordered sparse graphs
- Erdős-Hajnal-type results for monotone paths
- Nearly-linear monotone paths in edge-ordered graphs
- Non-crossing monotone paths and binary trees in edge-ordered complete geometric graphs
- The depression of a graph and \(k\)-kernels
- Trees with depression three
- A class of graphs with depression three
- Oscillation of graphs
- Finding monotone paths in edge-ordered graphs
This page was built for publication: A monotone path in an edge-ordered graph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1095926)
