Fractional chromatic number, maximum degree and girth
Nombre chromatique fractionnaire, degré maximum et maille
Résumé
We introduce a new method for computing bounds on the independence number and fractional chromatic number of classes of graphs with local constraints, and apply this method in various scenarios. We prove that if G is a triangle-free graph with maximum degree $Δ ≥ 2$, then its fractional chromatic number is at most 1$+(1+2/ln(Δ)) · Δ/(ln(Δ) - 2ln(ln(Δ)))$. This matches the best asymptotic upper bound known for off-diagonal Ramsey numbers, and is the first explicit bound of this nature. It is obtained as a corollary of a general upper bound on the fractional chromatic number of triangle-free graphs, which matches, for small values of the maximum degree $Δ$, that deduced from the fractional version of Reed's bound for triangle-free graphs, and improves it when $Δ ≥ 17$, transitioning smoothly to the correct asymptotic regime. 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 : 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)