Tiling edge-ordered graphs with monotone paths and other structures
Preprint
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.
Keywords
All Related Versions
This publication has 10 references indexed in Scilit:
- Dirac-type results for tilings and coverings in ordered graphsForum of Mathematics, Sigma, 2022
- Tilings in vertex ordered graphsJournal of Combinatorial Theory, Series B, 2022
- Nearly-linear monotone paths in edge-ordered graphsIsrael Journal of Mathematics, 2020
- Monotone paths in dense edge-ordered graphsJournal of Combinatorics, 2017
- The minimum degree threshold for perfect graph packingsCombinatorica, 2009
- H-Factors in Dense GraphsJournal of Combinatorial Theory, Series B, 1996
- Decomposition of large combinatorial structuresArchiv der Mathematik, 1989
- Increasing sequences with nonzero block sums and increasing paths in edge-ordered graphsDiscrete Mathematics, 1984
- Increasing paths in edge ordered graphsPeriodica Mathematica Hungarica, 1973
- On the maximal number of independent circuits in a graphActa Mathematica Hungarica, 1963