Turán problem for edge-ordered graphs.

Abstract:

The Turán-type extremal problem asks how many edges an n-vertex simple graph can have if it does not contain a subgraph isomorphic to a forbidden graph. The systematic study of Turán-type extremal problems for edge-ordered graphs was initiated by Gerbner, Methuku, Nagy, Pálvölgyi, Tardos, and Vizer in 2020. A simple graph is called edge-ordered if its edges are linearly ordered.

Gerbner et al. defined a parameter called order chromatic number for edge-ordered graphs and proved an Erdős-Stone-Simonovits-type theorem for edge ordered graphs that determines the Turán number of an edge-ordered graph having order chromatic number larger than 2.

In this talk we establish an upper bound of n2^{O(\sqrt{\log n})}} on the extremal function of edge-ordered forests of order chromatic number 2. Moreover, we also characterize connected edge-ordered graphs with linear extremal functions and show that the extremal function of other connected edge-ordered graphs is Ω(n log n).

Posted on Nov 20, 2024 in Seminario de Grafos, Seminars