Tiling Edge-Ordered Graphs with Monotone Paths and Other Structures
Authors:
- 7 June 2024
- journal article
- research article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 38 (2) , 1808-1839
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.Keywords
All Related Versions
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:
- Nearly-linear monotone paths in edge-ordered graphsIsrael Journal of Mathematics, 2020
- Statistics of orderingsAbhandlungen aus dem Mathematischen Seminar der Universitat Hamburg, 2017
- $F$ F -Factors in Hypergraphs Via AbsorptionGraphs and Combinatorics, 2014
- The minimum degree threshold for perfect graph packingsCombinatorica, 2009
- Tiling Turán TheoremsCombinatorica, 2000
- 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