A Characterization of Edge-Ordered Graphs with Almost Linear Extremal Functions.

The systematic study of Turán-type extremal problems for edge-ordered graphs was initiated by Gerbner et al. (Turán problems for Edge-ordered graphs, 2021). They conjectured that the extremal functions of edge-ordered forests of order chromatic number 2 are n 1 + o (1) . Here we resolve this conjecture proving the stronger upper bound of n 2 O (log n) . This represents a gap in the family of possible extremal functions as other forbidden edge-ordered graphs have extremal functions Ω (n c) for some c > 1 . However, our result is probably not the last word: here we conjecture that the even stronger upper bound of n log O (1) n also holds for the same set of extremal functions. [ABSTRACT FROM AUTHOR]