Akademska digitalna zbirka SLovenije - logo
VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
PDF
  • Dichromatic number and fractional chromatic number [Elektronski vir]
    Mohar, Bojan, 1956- ; Wu, Hehui
    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, P. Erdős and V. 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 ▫$\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.
    Vir: Forum of mathematics [Elektronski vir]. Sigma. - ISSN 2050-5094 (Vol. 4, art. no. e32, 2016, str. 1-14)
    Vrsta gradiva - e-članek
    Leto - 2016
    Jezik - angleški
    COBISS.SI-ID - 18211161

    Povezava(-e):

    https://doi.org/10.1017/fms.2016.28
    DOI

Vnos na polico