DICHROMATIC NUMBER AND FRACTIONAL CHROMATIC NUMBER. (15th December 2016) - MOHAR, BOJAN; WU, HEHUI
Abstract : The dichromatic number of a graph $G$ is the maximum integer $k$ such that there exists an orientation of the edges of $G$ such that for every partition of the vertices into fewer than $k$ parts, at least one of the parts must contain a directed cycle under this orientation. In 1979, Erdő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 a 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 $t$, then the fractional version of the dichromatic number of the graph is at least ${\textstyle \frac{1}{4}}t/\log _{2}(2et^{2})$ . This bound is best possible up to a small constant factor. Several related results of independent interest are given.