Edge ordered Turán problems

Main Article Content

Dániel Gerbner Abhishek Methuku Dániel T. Nagy Dömötör Pálvölgyi Gábor Tardos Máté Vizer


We introduce the Tur\'an problem for edge ordered graphs. We call a simple graph \emph{edge ordered}, if its edges are linearly ordered. An isomorphism between edge ordered graphs must respect the edge order. A subgraph of an edge ordered graph is itself an edge ordered graph with the induced edge order. We say that an edge ordered graph $G$ \emph{avoids} another edge ordered graph $H$, if no subgraph of $G$ is isomorphic to $H$. The Tur\'an number $\mathrm{ex}'_{<}(n,\mathcal{H})$ of a family $\mathcal{H}$ of edge ordered graphs is the maximum number of edges in an edge ordered graph on $n$ vertices that avoids all elements of $\mathcal{H}$. We examine this parameter in general and also for several singleton families of edge orders of certain small specific graphs, like star forests, short paths and the cycle of length four.

Article Details

How to Cite
Gerbner, D., Methuku, A., Nagy, D., Pálvölgyi, D., Tardos, G., & Vizer, M. (2019). Edge ordered Turán problems. Acta Mathematica Universitatis Comenianae, 88(3), 717-722. Retrieved from http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/article/view/1265/717