Back to Search
Start Over
Counting H -free orientations of graphs.
- Source :
-
Mathematical Proceedings of the Cambridge Philosophical Society . Jan2023, Vol. 174 Issue 1, p79-95. 17p. - Publication Year :
- 2023
-
Abstract
- In 1974, Erdős posed the following problem. Given an oriented graph H , determine or estimate the maximum possible number of H -free orientations of an n -vertex graph. When H is a tournament, the answer was determined precisely for sufficiently large n by Alon and Yuster. In general, when the underlying undirected graph of H contains a cycle, one can obtain accurate bounds by combining an observation of Kozma and Moran with celebrated results on the number of F -free graphs. As the main contribution of the paper, we resolve all remaining cases in an asymptotic sense, thereby giving a rather complete answer to Erdős's question. Moreover, we determine the answer exactly when H is an odd cycle and n is sufficiently large, answering a question of Araújo, Botler and Mota. [ABSTRACT FROM AUTHOR]
- Subjects :
- *UNDIRECTED graphs
*TOURNAMENTS
Subjects
Details
- Language :
- English
- ISSN :
- 03050041
- Volume :
- 174
- Issue :
- 1
- Database :
- Academic Search Index
- Journal :
- Mathematical Proceedings of the Cambridge Philosophical Society
- Publication Type :
- Academic Journal
- Accession number :
- 160865983
- Full Text :
- https://doi.org/10.1017/S0305004122000147