Résumé

We introduce the Turan problem for edge ordered graphs. We call a simple graph 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 avoids another edge ordered graph H, if no subgraph of G is isomorphic to H. The Turan number ex(<)'(n, H) of a family H of edge ordered graphs is the maximum number of edges in an edge ordered graph on n vertices that avoids all elements of 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.

Détails