2020/05/27 by Araújo, Pedro, Botler, Fábio, Mota, Guilherme Oliveira
#05C35 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2005.13091
Alon and Yuster proved that the number of orientations of any n-vertex graph in which every K3 is transitively oriented is at most 2\lfloor n2/4\rfloor for n ≥ 104 and conjectured that the precise lower bound on n should be n ≥ 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 n2/4\rfloor such orientations.