Geodesic
Dirac-type results for tilings and coverings in ordered graphs
Forum of Mathematics, Sigma, Tome 10 (2022)

Voir la notice de l'article provenant de la source Cambridge University Press

A recent paper of Balogh, Li and Treglown [3] initiated the study of Dirac-type problems for ordered graphs. In this paper, we prove a number of results in this area. In particular, we determine asymptotically the minimum degree threshold for forcing (i) a perfect H-tiling in an ordered graph, for any fixed ordered graph H of interval chromatic number at least $3$;(ii) an H-tiling in an ordered graph G covering a fixed proportion of the vertices of G (for any fixed ordered graph H);(iii) an H-cover in an ordered graph (for any fixed ordered graph H).The first two of these results resolve questions of Balogh, Li and Treglown, whilst (iii) resolves a question of Falgas-Ravry. Note that (i) combined with a result from [3] completely determines the asymptotic minimum degree threshold for forcing a perfect H-tiling. Additionally, we prove a result that, combined with a theorem of Balogh, Li and Treglown, asymptotically determines the minimum degree threshold for forcing an almost perfect H-tiling in an ordered graph (for any fixed ordered graph H). Our work therefore provides ordered graph analogues of the seminal tiling theorems of Kühn and Osthus [Combinatorica 2009] and of Komlós [Combinatorica 2000]. Each of our results exhibits some curious, and perhaps unexpected, behaviour. Our solution to (i) makes use of a novel absorbing argument. 
@article{10_1017_fms_2022_92,
     author = {Andrea Freschi and Andrew Treglown},
     title = {Dirac-type results for tilings and coverings in ordered graphs},
     journal = {Forum of Mathematics, Sigma},
     publisher = {mathdoc},
     volume = {10},
     year = {2022},
     doi = {10.1017/fms.2022.92},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1017/fms.2022.92/}
}
TY  - JOUR
AU  - Andrea Freschi
AU  - Andrew Treglown
TI  - Dirac-type results for tilings and coverings in ordered graphs
JO  - Forum of Mathematics, Sigma
PY  - 2022
VL  - 10
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.1017/fms.2022.92/
DO  - 10.1017/fms.2022.92
LA  - en
ID  - 10_1017_fms_2022_92
ER  - 
%0 Journal Article
%A Andrea Freschi
%A Andrew Treglown
%T Dirac-type results for tilings and coverings in ordered graphs
%J Forum of Mathematics, Sigma
%D 2022
%V 10
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.1017/fms.2022.92/
%R 10.1017/fms.2022.92
%G en
%F 10_1017_fms_2022_92
Andrea Freschi; Andrew Treglown. Dirac-type results for tilings and coverings in ordered graphs. Forum of Mathematics, Sigma, Tome 10 (2022). doi: 10.1017/fms.2022.92

Cité par Sources :