Tiling Edge-Ordered Graphs with Monotone Paths and Other Structures

Authors:

Abstract
Given graphs [Formula: see text] and [Formula: see text], a perfect [Formula: see text]-tiling in [Formula: see text] is a collection of vertex-disjoint copies of [Formula: see text] in [Formula: see text] that together cover all the vertices in [Formula: see text]. The study of the minimum degree threshold forcing a perfect [Formula: see text]-tiling in a graph [Formula: see text] has a long history, culminating in the Kühn–Osthus theorem [D. Kühn and D. Osthus, Combinatorica, 29 (2009), pp. 65–107] which resolves this problem, up to an additive constant, for all graphs [Formula: see text]. In this paper we initiate the study of the analogous question for edge-ordered graphs. In particular, we characterize for which edge-ordered graphs [Formula: see text] this problem is well-defined. We also apply the absorbing method to asymptotically determine the minimum degree threshold for forcing a perfect [Formula: see text]-tiling in an edge-ordered graph, where [Formula: see text] is any fixed monotone path.
Funding Information
  • University of Birmingham
  • University of Illinois at Urbana-Champaign (RB 22000)
  • Engineering and Physical Sciences Research Council (EP/V002279/1)

This publication has 16 references indexed in Scilit: