省略非边临界有向图的图的定向问题

Orientations of graphs omitting non-edge-critical directed graphs

摘要 Abstract

1974年,Erdős提出了以下问题:给定一个图$G$和一个有向图$\vec{H}$,有多少种方法可以对$G$的边进行定向,使得它不包含$\vec{H}$作为子图?我们将这个值记为$D(G, \vec{H})$。进一步地,我们令$D(n, \vec{H})$表示在所有具有$n$个顶点的图$G$上,$D(G, \vec{H})$的最大值。2006年,Alon和Yuster给出了当$\vec{H}$为竞赛图时的精确答案。2023年,Bucić、Janzer和Sudakov给出了所有有向图$\vec{H}$的渐近解,并在同一论文中给出了当$\vec{H}$为有向循环时的精确解。本文对某些特定的非二分有向图给出了更好的界值。此外,对于一些小的非边临界有向图$\vec{H}$,我们得到了$D(G, \vec{H})$的确切值。最后,对于这些图,我们分类了所有达到界值$D(G, \vec{H}) = D(n, \vec{H})$的图$G$。

In 1974, Erd\H{o}s asked the following question: given a graph $G$ and a directed graph $\vec{H}$, how many ways are there to orient the edges of $G$ such that it does not contain $\vec{H}$ as a subgraph? We denote this value by $D(G, \vec{H})$. Further, we let $D(n, \vec{H})$ denote the maximum of $D(G, \vec{H})$ over all graphs $G$ on $n$ vertices. In 2006, Alon and Yuster gave an exact answer when $\vec{H}$ is a tournament. In 2023, Buci\'c, Janzer, and Sudakov gave asymptotic answers for all directed graphs $\vec{H}$, and in the same paper, they gave an exact answer when $\vec{H}$ 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 $D(G, \vec{H})$ for some small non-edge-critical directed graphs $\vec{H}$. Finally, for these graphs, we classify all graphs $G$ that attain the bound $D(G, \vec{H}) = D(n, \vec{H})$.

省略非边临界有向图的图的定向问题 - arXiv