Fractional chromatic number, maximum degree and girth

Nombre chromatique fractionnaire, degré maximum et maille

François Pirot (1, 2) , Jean-Sébastien Sereni (3, 4)

1 ORPAILLEUR - Knowledge representation, reasonning
2 Radboud University [Nijmegen]
3 CNRS - Centre National de la Recherche Scientifique
4 ICube - Laboratoire des sciences de l'ingénieur, de l'informatique et de l'imagerie

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].

Domaines: Combinatoire [math.CO]; Mathématique discrète [cs.DM]

François Pirot, Jean-Sébastien Sereni. Fractional chromatic number, maximum degree and girth. 2019. ⟨hal-02096426v3⟩