Tiling edge-ordered graphs with monotone paths and other structures
| Autor: | Araujo, Igor, Piga, Simón, Treglown, Andrew, Xiang, Zimu |
|---|---|
| Rok vydání: | 2023 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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\"uhn--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. Comment: 29 pages. We have made a number of updates to the paper, particularly in the concluding remarks section |
| Databáze: | arXiv |
| Externí odkaz: |
|