Beyond the fractional Reed bound for triangle-free graphs
Time: 14:00 -- Location: LRI, 445
summary: The notion of fractional colouring is an important concept in graph theory that is commonly used to extend the notion of graph colouring beyond integer values. It is a relaxation of the traditional chromatic number, allowing for real-valued weights or probabilities associated with each independent set of a graph. We are interested in the value of χ_f(d,△), the supremum of the fractional chromatic number over all triangle-free graphs of maximum degree at most d. It has been settled by Dvořák, Sereni, and Volec that χ_f(d,△)=2.8, and the next open case is d=4. In 2002, Molloy and Reed proved that χ_f(d,△) ≤ (d+3)/2 for every integer d, which implies that χ_f(4,△) ≤ 3.5. However, it is conjectured that χ_f(4,△) = 3.25. In this talk, we prove that χ_f(4,△) ≤ 3.4663. We rely on a methodology introduced by Pirot and Sereni that lets us use a probability distribution over the independent sets of a graph G in order to obtain a fractional colouring of G. We will show how to use mixed probability distributions with that method in order to increase its efficiency.