{"id":"arxiv/2604.05228","url":"https://arxiv.org/abs/2604.05228","tags":["math.LO"],"score":0,"title":"No Countable Basis for Borel Directed Graphs of Dichromatic Number at Least Three","domain":"math.LO","source":"arxiv","authors":["Tonatiuh Matos-Wiederhold"],"reviews":0,"subject":"math.LO","summary":"I prove that the Borel directed graphs whose vertex set admits a partition into two Borel acyclic sets form a $\\mathbfΣ^1_2$-complete set; equivalently, that deciding whether a Borel directed graph has Borel dichromatic number at least~$3$ is a $\\mathbfΠ^1_2$-complete problem. It follows that no countable family of Borel directed graphs can serve as a basis for this class under Borel homomorphism and, more generally, that any basis must be at least as complex as~$\\mathbfΠ^1_2$. The proof lifts the classical NP-completeness reduction of Bokal, Fijavž, Juvan, Kayll, and Mohar to the Borel…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-04-06","reactions":{}}