Tiling problems in edge-ordered graphs

Igor Araujo; Simon Piga; Andrew Treglown; Zimu Xiang

doi:10.5817/CZ.MUNI.EUROCOMB23-010

Tiling problems in edge-ordered graphs

Igor Araujo, Simon Piga, Andrew Treglown, Zimu Xiang

Mathematics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

31 Downloads (Pure)

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

Original language	English
Title of host publication	EUROCOMB’23
Publisher	Masaryk University Press
Pages	1-8
Number of pages	8
DOIs	https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-010
Publication status	Published - 28 Aug 2023
Event	European Conference on Combinatorics, Graph Theory and Applications - Charles University, Faculty of Mathematics and Physics, Prague, Czech Republic Duration: 28 Aug 2023 → 1 Sept 2023 https://iuuk.mff.cuni.cz/events/conferences/eurocomb23/

Publication series

Name	European Conference on Combinatorics, Graph Theory and Applications
Publisher	Masaryk University Press
Number	12
ISSN (Electronic)	2788-3116

Conference

Conference	European Conference on Combinatorics, Graph Theory and Applications
Abbreviated title	EUROCOMB'23
Country/Territory	Czech Republic
City	Prague
Period	28/08/23 → 1/09/23
Internet address	https://iuuk.mff.cuni.cz/events/conferences/eurocomb23/

Access to Document

10.5817/CZ.MUNI.EUROCOMB23-010Licence: Creative Commons: Attribution-NonCommercial-NoDerivs (CC BY-NC-ND)

AraujoI2023TilingFinal published version, 418 KBLicence: Creative Commons: Attribution-NonCommercial-NoDerivs (CC BY-NC-ND)

Matchings and tilings in graphs
Lo, A. (Co-Investigator) & Treglown, A. (Principal Investigator)
Engineering & Physical Science Research Council
1/03/21 → 29/02/24
Project: Research Councils

Cite this

@inproceedings{fbc7a4c2cc0047bca3e99e796703d063,

title = "Tiling problems in edge-ordered graphs",

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{\"u}hn–Osthus theorem [Combinatorica 2009] which resolves this problem, up to an additive constant, for all graphs F. 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. ",

author = "Igor Araujo and Simon Piga and Andrew Treglown and Zimu Xiang",

year = "2023",

month = aug,

day = "28",

doi = "10.5817/CZ.MUNI.EUROCOMB23-010",

language = "English",

series = "European Conference on Combinatorics, Graph Theory and Applications",

publisher = "Masaryk University Press",

number = "12",

pages = "1--8",

booktitle = "EUROCOMB{\textquoteright}23",

note = "European Conference on Combinatorics, Graph Theory and Applications, EUROCOMB'23 ; Conference date: 28-08-2023 Through 01-09-2023",

url = "https://iuuk.mff.cuni.cz/events/conferences/eurocomb23/",

}

Araujo, I, Piga, S, Treglown, A & Xiang, Z 2023, Tiling problems in edge-ordered graphs. in EUROCOMB’23., 10, European Conference on Combinatorics, Graph Theory and Applications, no. 12, Masaryk University Press, pp. 1-8, European Conference on Combinatorics, Graph Theory and Applications, Prague, Czech Republic, 28/08/23. https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-010

TY - GEN

T1 - Tiling problems in edge-ordered graphs

AU - Araujo, Igor

AU - Piga, Simon

AU - Treglown, Andrew

AU - Xiang, Zimu

PY - 2023/8/28

Y1 - 2023/8/28

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

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

UR - https://journals.muni.cz/eurocomb

U2 - 10.5817/CZ.MUNI.EUROCOMB23-010

DO - 10.5817/CZ.MUNI.EUROCOMB23-010

M3 - Conference contribution

T3 - European Conference on Combinatorics, Graph Theory and Applications

SP - 1

EP - 8

BT - EUROCOMB’23

PB - Masaryk University Press

T2 - European Conference on Combinatorics, Graph Theory and Applications

Y2 - 28 August 2023 through 1 September 2023

ER -

Tiling problems in edge-ordered graphs

Abstract

Publication series

Conference

Access to Document

Fingerprint

Projects

Matchings and tilings in graphs

Cite this