Out-colourings of Digraphs
Introduction
The study of graph partitioning is a cornerstone of combinatorics, often involving the division of a vertex set into classes that preserve or forbid certain structural properties. This paper investigates the concept of out-colourings in directed graphs (digraphs). An out-colouring is a vertex colouring such that no vertex has a monochromatic set of outgoing neighbours. In the fundamental case of a 2-out-colouring, the vertex set is partitioned into two sets, $V_1$ and $V_2$, such that every vertex $v$ has at least one out-neighbour in $V_1$ and at least one out-neighbour in $V_2$.
While the problem of finding such colourings is computationally difficult in general, the authors demonstrate that the dense, rigid structure of tournaments and semicomplete digraphs allows for more definitive guarantees.
Methodology
The research employs a dual-pronged approach combining structural graph theory with probabilistic methods:
- Structural Analysis and Complexity: The authors establish that deciding if a general digraph admits a 2-out-colouring is NP-complete. This is achieved through polynomial-time reductions from known hard problems like Monotone NAE-3-SAT. For specific classes like tournaments, they perform an exhaustive structural characterization of small graphs to identify exactly which configurations permit or obstruct out-colourings.
- The Probabilistic Method and Discrepancy Theory: To address the generalized $k$-partition problem—where every vertex must have at least $k$ out-neighbours in each partition—the authors turn to probabilistic techniques. By randomly assigning vertices to partitions and applying Chernoff bounds, they prove existence for large tournaments. To achieve perfectly balanced partitions, they integrate discrepancy theory, specifically utilizing variants of Spencer’s "six standard deviations" theorem combined with entropy arguments.
Key Insights and Ideas
A primary finding is that high minimum out-degree does not guarantee an out-colouring in general digraphs. The authors construct bipartite tournaments with arbitrarily large out-degrees that remain impossible to 2-out-colour.
However, tournaments are significantly more constrained. For these graphs, a minimum out-degree of just 3 is sufficient to guarantee a 2-out-colouring, with the 7-vertex Paley tournament ($P_7$) being the sole exception. Furthermore, the authors show that if a semicomplete digraph can be 2-out-coloured, it can almost always be done so in a balanced manner (where the sizes of the two colour classes differ by at most one).
The transition from 2-colouring to $k$-partitions reveals a deeper connection to statistical fluctuations. The required minimum out-degree for a $k$-partition is shown to be $2k + \Theta(\sqrt{k})$. The $\sqrt{k}$ term is a direct consequence of the discrepancy inherent in random splits, representing the natural statistical fluctuations that must be overcome to ensure every vertex meets the out-degree threshold in every partition.
Key Results
- Complexity Bounds: The problem of 2-out-colouring is proven NP-complete for general digraphs, symmetric digraphs, and bipartite tournaments.
- Characterization of Tournaments: The paper provides a complete, polynomial-time decidable characterization for tournaments and semicomplete digraphs with minimum out-degree 2 that admit a 2-out-colouring.
- Asymptotically Tight $k$-Partitioning: The authors prove that there exists a constant $c_1$ such that every tournament with minimum out-degree at least $2k + c_1\sqrt{k}$ admits a balanced 2-partition where every vertex has at least $k$ out-neighbours in both sets. This bound is shown to be asymptotically optimal.
Conclusion and Future Directions
This work highlights the stark contrast between general digraphs and tournaments regarding out-colouring properties. While the probabilistic method provides sharp asymptotic bounds, the authors note that determining optimal constants for small $k$ or for partitions into more than two sets remains an open challenge. Future research may extend these results to other classes of oriented graphs, such as those with bounded independence numbers, to see if similar guarantees hold.
Summary updated