2023/09/19 by Gaurav Kucheriya, Gábor Tardos, Kucheriya, Gaurav +1
Computer Science · Mathematics · #05C35 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph theory and applications
paper · pdf · doi:10.48550/arxiv.2309.10558
openalex publication_date 2023/09/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
The systematic study of Turán-type extremal problems for edge-ordered graphs was initiated by Gerbner et al. in 2020. Here we characterize connected edge-ordered graphs with linear extremal functions and show that the extremal function of other connected edge-ordered graphs is Ω(nlog n). This characterization and dichotomy are similar in spirit to results of Füredi et al. (2020) about vertex-ordered and convex geometric graphs. We also extend the study of extremal function of short edge-ordered paths by Gerbner et al. to some longer paths.