# zbMATH — the first resource for mathematics

Monotone paths in edge-ordered sparse graphs. (English) Zbl 0961.05040
An edge-ordered graph is an ordered pair $$(G,f)$$, where $$G=G(V,E)$$ is a graph and $$f$$ is a bijective function $$f:E(G)\to \{1,2,\dots,|E(G)|\}$$. $$f$$ is called an edge ordering of $$G$$. A monotone path of length $$k$$ in $$(G,f)$$ is a simple path $$P_{k+1}:v_1,v_2,\dots,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_{i+1}))>f((v_{i+1},v_{i+2}))$$ for $$i=1,2,\dots,k-1$$. Given an undirected graph $$G$$, denote by $$\alpha(G)$$ the minimum over all edge orderings of the maximum length of a monotone path. The authors give bounds on $$\alpha(G)$$ for various families of sparse graphs, including trees, planar graphs and graphs with bounded arboricity. For example, every planar graph $$G$$ has $$\alpha(G)\leq 9$$, and every bipartite planar graph $$G$$ has $$\alpha(G)\leq 6$$.

##### MSC:
 05C38 Paths and cycles
##### Keywords:
sparse graphs; monotone path; linear arboricity; star arboricity
Full Text: