DICHROMATIC NUMBER AND FRACTIONAL CHROMATIC NUMBER
Forum of Mathematics, Sigma, Tome 4 (2016)
Voir la notice de l'article provenant de la source Cambridge University Press
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.
@article{10_1017_fms_2016_28,
author = {BOJAN MOHAR and HEHUI WU},
title = {DICHROMATIC {NUMBER} {AND} {FRACTIONAL} {CHROMATIC} {NUMBER}},
journal = {Forum of Mathematics, Sigma},
publisher = {mathdoc},
volume = {4},
year = {2016},
doi = {10.1017/fms.2016.28},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.1017/fms.2016.28/}
}
BOJAN MOHAR; HEHUI WU. DICHROMATIC NUMBER AND FRACTIONAL CHROMATIC NUMBER. Forum of Mathematics, Sigma, Tome 4 (2016). doi: 10.1017/fms.2016.28
Cité par Sources :