Extremal Theory of Edge-ordered Graphs

An edge-ordered graph – as the name suggests – is a simple graph with a linear order on its edge set.

As an extension of Turán-type extremal graph theory we ask for the largest number ex(n,H) of edges an n-vertex edge-ordered graph can have if it does not contain the forbidden edge-ordered graph H. In other words, we forbid a subgraph only with a specified edge-order.

A related model of vertex-ordered graphs has been studied earlier but the edge-ordered variant was introduced as late 2023 in a paper with Gerbner, Methuku, Nagy, Pálvölgyi, and Vizer. We found that the variant of the Erdős-Stone-Simonovits theorem holds in this model also, but with several subtle changes. As in the classical case, the extremal number ex(n,H) is determined asymptotically by the chromatic number of H if it’s more than two. But this chromatic number is strange in that it

– can be infinite for a finite edge-ordered graph

– even if finite, can be much larger than the graph,

– is unknown for a certain 4-vertex edge-ordered graph, and

– if defined for a family of (forbidden) edge-ordered graphs it can be much less than for any single member of the family.

The survey will include some more recent results we had with Gaurav Kucheriya on the complexity of calculating the chromatic number of edge-ordered graphs.