Tiling edge-ordered graphs with monotone paths and other structures

MaRDI QIDQ6436356zbMATH OpenFDO

Authors Igor Araujo, Simón Piga, Andrew Treglown, Zimu Xiang

Publication date 12 May 2023

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"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.

This page was built for publication: Tiling edge-ordered graphs with monotone paths and other structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6436356)