@article{95ff480f46a64c05a02445e75151133e,
title = "Tur{\'a}n problems for edge-ordered graphs",
abstract = "In this paper we initiate a systematic study of the Tur{\'a}n problem for edge-ordered graphs. A simple graph is called edge-ordered if its edges are linearly ordered. This notion allows us to study graphs (and in particular their maximum number of edges) when a subgraph is forbidden with a specific edge-order but the same underlying graph may appear with a different edge-order. We prove an Erd{\H o}s-Stone-Simonovits-type theorem for edge-ordered graphs—we identify the relevant parameter for the Tur{\'a}n number of an edge-ordered graph and call it the order chromatic number. We establish several important properties of this parameter. We also study Tur{\'a}n numbers of edge-ordered paths, star forests and the cycle of length four. We make strong connections to Davenport-Schinzel theory, the theory of forbidden submatrices, and show an application in discrete geometry.",
keywords = "Discrete geometry, Edge ordered graphs, Erd{\H o}s-Stone-Simonovits theorem, Extremal combinatorics, Forbidden submatrices, Graph theory, Tur{\'a}n's theorem",
author = "D{\'a}niel Gerbner and Abhishek Methuku and Nagy, {D{\'a}niel T.} and D{\"o}m{\"o}t{\"o}r P{\'a}lv{\"o}lgyi and G{\'a}bor Tardos and M{\'a}t{\'e} Vizer",
note = "The research of D{\'a}niel Gerbner was supported by the J{\'a}nos Bolyai Research Fellowship of the Hungarian Academy of Sciences and the National Research, Development and Innovation Office – NKFIH under the grants FK 132060 , K 116769 , KH130371 , KKP-133819 and SNN 129364 . The research of Abhishek Methuku was supported by the EPSRC , grant no. EP/S00100X/1 , by the Institute of Basic Sciences grant number IBS-R029-C1 and by the National Research, Development and Innovation Office - NKFIH under the grant K 116769 . The research of D{\'a}niel T. Nagy was supported by the National Research, Development and Innovation Office - NKFIH under the grants K 116769 , K 132696 , PD 137779 and FK 132060 , and by the J{\'a}nos Bolyai Research Fellowship of the Hungarian Academy of Sciences . The research of D{\"o}m{\"o}t{\"o}r P{\'a}lv{\"o}lgyi was supported by the Lend{\"u}let program LP2017-19/2017 and by the J{\'a}nos Bolyai Research Scholarship of the Hungarian Academy of Sciences , and by the New National Excellence Program {\'U}NKP-22-5 and by the Thematic Excellence Program TKP2021-NKTA-62 of the National Research, Development and Innovation Office . The research of G{\'a}bor Tardos was supported by the National Research, Development and Innovation Office projects K-132696 and SNN-135643 and by the ERC Advanced Grant “GeoScape.” The research of M{\'a}t{\'e} Vizer was supported by the Hungarian National Research, Development and Innovation Office – NKFIH under the grant SNN 129364 , KH 130371 and KF 132060 by the J{\'a}nos Bolyai Research Fellowship of the Hungarian Academy of Sciences and by the New National Excellence Program under the grant number {\'U}NKP-19-4-BME-287 .",
year = "2023",
month = may,
doi = "10.1016/j.jctb.2022.12.006",
language = "English (US)",
volume = "160",
pages = "66--113",
journal = "Journal of Combinatorial Theory. Series B",
issn = "0095-8956",
publisher = "Academic Press Inc.",
}