The dichromatic number of a graph is the maximum integer such that there exists an orientation of the edges of such that for every partition of the vertices into fewer than parts, at least one of the parts must contain a directed cycle under this orientation. In 1979, Erd\H{o}s and Neumann-Lara conjectured that if the dichromatic number of a graph is bounded, so is its chromatic number. We make the first significant progress on this conjecture by proving a fractional version of the conjecture. While our result uses stronger assumption about the fractional chromatic number, it also gives a much stronger conclusion: If the fractional chromatic number of a graph is at least , then the fractional version of the dichromatic number of the graph is at least . This bound is best possible up to a small constant factor. Several related results of independent interest are given.

生成讲解博客的中文版本

生成AI智能校验的中文版本