Counting odd cycle free orientations of graphs

2020/06/02 by Bucić, M., Sudakov, B.
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2006.01670

Abstract

In this short note we determine the maximum number, over all n-vertex graphs G, of orientations of G containing no strongly connected cycle C_2k+1. This answers a part of a recent question of Araujo, Botler and Mota.

Related

• Counting H-free orientations of graphs
• Counting orientations of graphs with no strongly connected tournaments
• Orientations making k-cycles cyclic
• Arbitrary orientations of cycles in oriented graphs
• Alternating odd cycles and orientations of Kneser-like graphs