




















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 establish a formula that generates a general upper bound for the fractional chromatic number of triangle-free graphs of maximum degree~$Δ\ge 3$. This upper bound matches that deduced from the fractional version of Reed's bound for small values of~$Δ$, and improves it when~$Δ\ge 17$, transitioning smoothly to the best possible asymptotic regime, barring a breakthrough in Ramsey theory. 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~$1+ \min_{k \in \mathbb{N}} \frac{2Δ+ 2^{k-3}}{k}$. In particular, the fractional chromatic number of a graph of girth~$7$ and maximum degree~$Δ$ is at most~$\frac{2Δ+9}{5}$ when~$Δ\in [3,8]$, at most~$\frac{Δ+7}{3}$ when~$Δ\in [8,20]$, at most~$\frac{2Δ+23}{7}$ when~$Δ\in [20,48]$, and at most~$\fracΔ{4}+5$ when~$Δ\in [48,112]$. In addition, we also obtain new lower bounds on the independence ratio of graphs of maximum degree~$Δ\in \{3,4,5\}$ and girth~$g\in \{6,\dotsc,12\}$, notably~$1/3$ when~$(Δ,g)=(4,10)$ and~$2/7$ when~$(Δ,g)=(5,8)$.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。