DICHROMATIC NUMBER AND FRACTIONAL CHROMATIC NUMBER. (15th December 2016)

• Record Type: Journal Article
• Authors: MOHAR, BOJAN; WU, HEHUI
• Is Part Of: Forum of mathematics. Volume 4(2016)
• Publication Date: 2016-12-15
• Subjects: 05C15; Mathematics -- Periodicals; 510
• DOI: 10.1017/fms.2016.28
• Languages: English
• ISSNs: 2050-5094

Abstract

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.