Tur\'an problems for oriented graphs

Abstract: A classical Tur'an problem asks for the maximum possible number of edges in a graph of a given order that does not contain a particular graph

H

as a subgraph. It is well-known that the chromatic number of

H

is the graph parameter which describes the asymptotic behavior of this maximum. Here, we consider an analogous problem for oriented graphs, where compressibility plays the role of the chromatic number. Since any oriented graph having a directed cycle is not contained in any transitive tournament, it makes sense to consider only acyclic oriented graphs as forbidden subgraphs. We provide basic properties of the compressibility, show that the compressibility of acyclic oriented graphs with out-degree at most 2 is polynomial with respect to the maximum length of a directed path, and that the same holds for a larger out-degree bound if the ErdH{o}s-Hajnal conjecture is true. Additionally, generalizing previous results on powers of paths and arbitrary orientations of cycles, we determine the compressibility of acyclic oriented graphs with a restricted structure.

This page was built for publication: Tur\'an problems for oriented graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6438685)