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

Yihang Liu; Zhenyu Yang; Yuwan Zhang

In the authors' words

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 Gallai--Roy-type bound $χ_{a} (D) \leq L (D)$ , where $L (D)$ is the maximum order of a directed path. Let $r = lo g_{2} (8/7)$ . Bang-Jensen, Picasarri-Arrieta, and Yeo previously constructed tournaments of order $n$ whose acyclic dichromatic number is at least $n - (\frac{8}{r}) lo g_{2} n - lo g_{2} lo g_{2} n$ . We improve the leading logarithmic coefficient by a factor of two: for the uniform random tournament $T_{n}$ , asymptotically almost surely, $χ_{a} (T_{n}) \geq n - \frac{4}{r} lo g_{2} n + \frac{2}{r} lo g_{2} lo g_{2} n - O (1)$ . Finally, if $m (k)$ denotes the minimum order of an oriented graph with acyclic dichromatic number at least $k$ , tournament completion shows that the same minimum is obtained over tournaments. We prove $m (3) = 5$ and $m (4) = 7$ and classify the tournament witnesses at these minimum orders: there is one at order five and two at order seven.

Main resultThe abstract does not state a limitation.

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

In the authors' words

More on Combinatorics & discrete math that day

Circular s-choice parking functions: an exact closed formula via rotational symmetry

Single-Fragment Forensic Coding via Multidimensional Cyclically Permutable Codes

The Deterministic Broadcast Channel Revisited: A Bipartite Graph Approach

Proof of Almkvist's conjecture on the unimodality of partition polynomials

On infinite families of [Pn​]-irregular graphs

On infinite families of $[P_{n}]$ -irregular graphs