2023/05/12 by Igor Araújo, Araujo, Igor, Simón Piga +5 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2305.07294
openalex publication_date 2023/05/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.