In 1974, Erdős asked the following question: given a graph and a directed graph , how many ways are there to orient the edges of such that it does not contain as a subgraph? We denote this value by . Further, we let denote the maximum of over all graphs on vertices. In 2006, Alon and Yuster gave an exact answer when is a tournament. In 2023, Bucić, Janzer, and Sudakov gave asymptotic answers for all directed graphs , and in the same paper, they gave an exact answer when is a directed cycle. In this paper, we give a better bound for some specific non-bipartite directed graphs. Further, we obtain exact values of for some small non-edge-critical directed graphs . Finally, for these graphs, we classify all graphs that attain the bound .

生成讲解博客的中文版本

生成AI智能校验的中文版本