A characterization of edge-ordered graphs with almost linear extremal functions

The Turán-type extremal graph theory aims to determine the maximum number of edges in a simple graph without containing the forbidden subgraph H. Recently this problem has been studied for edge-ordered graphs which are simple graphs with a linear order on their edges by Gerbner, Methuku, Nagy, Pálvölgyi, Tardos and Vizer. In this talk we show that the extremal functions of edge-ordered forests of order chromatic number 2 is almost linear, whereas the extremal function of any other edge-ordered graph is at least n^c, for some c>1. In other words, we characterize the forbidden edge ordered graphs with almost linear extremal functions.