Fractional chromatic number, maximum degree and girth
Nombre chromatique fractionnaire, degré maximum et maille
Résumé
We prove new lower bounds on the independence ratio of graphs of maximum
degree ∆ ∈ {3,4,5} and girth g ∈ {6,…,12},
notably 1/3 when (∆,g)=(4,10) and 2/7 when (∆,g)=(5,8).
We establish a general upper bound on the fractional
chromatic number of triangle-free graphs, which implies that deduced from
the fractional version of Reed's bound for triangle-free graphs and improves
it as soon as ∆ ≥ 17, matching the best asymptotic upper bound
known for off-diagonal Ramsey numbers. In particular, the fractional
chromatic number of a triangle-free graph of maximum degree ∆ is
less than 9.916 if ∆=17,
less than 22.17 if ∆=50 and
less than 249.06 if ∆=1000.
Focusing on smaller values of ∆, we also demonstrate that every
graph of girth at least 7 and maximum degree ∆ has fractional
chromatic number at most min (2∆ + 2^{k-3}+k)/k pour k ∈ ℕ. In particular, the fractional chromatic number of a graph
of girth 7 and maximum degree ∆ is
at most (2∆+9)/5 when ∆ ∈ [3,8],
at most (∆+7)/3 when ∆ ∈ [8,20],
at most (2∆+23)/7 when ∆ ∈ [20,48], and
at most ∆/4+5 when ∆ ∈ [48,112].
Origine : Fichiers produits par l'(les) auteur(s)
Loading...