Alon and Yuster proved that the number of orientations of any $n$-vertex graph in which every $K_3$ is transitively oriented is at most $2^{lfloor n^2/4rfloor}$ for $n geq 10^4$ and conjectured that the precise lower bound on $n$ should be $n geq 8$. We confirm their conjecture and, additionally, characterize the extremal families by showing that the balanced complete bipartite graph with $n$ vertices is the only $n$-vertex graph for which there are exactly $2^{lfloor n^2/4rfloor}$ such orientations.
تحميل البحث