Counting graph orientations with no directed triangles

Abstract

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/4\rfloor }$ for $n\ge 10^4$ and conjectured that the precise lower bound on $n$ should be $n\ge 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/4\rfloor }$ such orientations.

Cited by in corpus (1)

• Counting odd cycle free orientations of graphs