Acyclic Dicolourings of Oriented Graphs: Paths, Random Tournaments, and Critical Orders

Yihang Liu, Zhenyu Yang, Yuwan Zhang

An acyclic dicolouring of an oriented graph is a vertex partition in which every colour class and every bipartite subdigraph induced by two classes is acyclic. We first prove the G…