Logic Seminar

The dichromatic number of a directed graph, a directed analogue of the chromatic number introduced by Neumann-Lara, is the minimum number of acyclic sets needed to partition its vertex set. Bokal et al. showed that deciding whether a finite digraph has dichromatic number at most 2 is NP-complete, in contrast with the undirected case where NP-completeness begins at 3 colors.

In the Borel setting, the complexity landscape for chromatic numbers is well understood: the G0-dichotomy of Kechris, Solecki, and Todorčević provides a one-element basis at the countable/uncountable threshold, the L0-dichotomy of Carroy, Miller, Schrittesser, and Vidnyánszky does the same at the 2-/3-color threshold, and Todorčević and Vidnyánszky showed that no basis can exist at any higher finite threshold. For the dichromatic number, Raghavan and Xiao recently established a continuum-size basis at the countable/uncountable threshold.

We complete the picture at finite thresholds: the set of Borel digraphs admitting a Borel 2-dicoloring is Sigma^1_2-complete, and consequently no countable basis exists for Borel digraphs of dichromatic number at least 3. Combined with a simple reduction from undirected to directed coloring, this settles the question for all finite thresholds of both the Borel chromatic and dichromatic numbers. The proof adapts the classical NP-completeness reduction to the Borel setting using Thornton's coding framework. We also discuss several open problems, including questions about bounded width CSPs and measurable arboricity.