Akademska digitalna zbirka SLovenije - logo
VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
  • Triangle-free subgraphs with large fractional chromatic number [Elektronski vir]
    Mohar, Bojan, 1956- ; Wu, Hehui
    It is well known that for any ▫$k$▫ and ▫$g$▫, there is a graph with chromatic number at least ▫$k$▫ and girth at least ▫$g$▫. In 1970's, Erdős and Hajnal conjectured that for any numbers ▫$k$▫ and ... ▫$g$▫, there exists a number ▫$f(k,g)$▫, such that every graph with chromatic number at least ▫$f(k, g)$▫ contains a subgraph with chromatic number at least ▫$k$▫ and girth at least ▫$g$▫. In 1978, Rödl proved the case for ▫$g=4$▫ and arbitrary ▫$k$▫. We prove the fractional chromatic number version of Rödl's result.
    Vir: The Eight European Conference on Combinatorics, Graph Theory and Applications, EuroComb 2015 [Elektronski vir] (Str. 661-666)
    Vrsta gradiva - prispevek na konferenci
    Leto - 2015
    Jezik - angleški
    COBISS.SI-ID - 17784409

    Povezava(-e):

    http://dx.doi.org/10.1016/j.endm.2015.06.089

Vnos na polico