Tiling edge-ordered graphs with monotone paths and other structures

Abstract

Given graphs $F$ and $G$, a perfect $F$-tiling in $G$ is a collection of vertex-disjoint copies of $F$ in $G$ that together cover all the vertices in $G$. The study of the minimum degree threshold forcing a perfect $F$-tiling in a graph $G$ has a long history, culminating in the Kühn--Osthus theorem [Combinatorica 2009] which resolves this problem, up to an additive constant, for all graphs $F$. In this paper we initiate the study of the analogous question for edge-ordered graphs. In particular, we characterize for which edge-ordered graphs $F$ this problem is well-defined. We also apply the absorbing method to asymptotically determine the minimum degree threshold for forcing a perfect $P$-tiling in an edge-ordered graph, where $P$ is any fixed monotone path.

29 pages. We have made a number of updates to the paper, particularly in the concluding remarks section