Fractional colorings of partial $t$-trees with no large clique

Abstract

Dvořák and Kawarabayashi [European Journal of Combinatorics, 2017] asked, what is the largest chromatic number attainable by a graph of treewidth $t$ with no $K_r$ subgraph? In this paper, we consider the fractional version of this question. We prove that if $G$ has treewidth $t$ and clique number $2\le \omega \le t$, then ${\chi }_f(G)\le t+\frac{\omega -1}{t}$, and we show that this bound is tight for $\omega =t$. We also show that for each value $0<c<\frac{1}{2}$, there exists a graph $G$ of a large treewidth $t$ and clique number $\omega =\lfloor (1-c)t\rfloor$ satisfying ${\chi }_f(G)\ge t+1+\frac{1}{2}\log (1-2c)+o(1)$, which is approximately equal to the upper bound for small values $c$.

arXiv comment9 pages