Dichromatic number and fractional chromatic number

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 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 $\frac{1}{4}t/{\log }_2(2e{t}^2)$. This bound is best possible up to a small constant factor. Several related results of independent interest are given.

Cited by in corpus (3)

• On the Complexity of Digraph Colourings and Vertex Arboricity
• Triangle-free subgraphs with large fractional chromatic number
• Fractional chromatic number of a random subgraph