Fractional colorings of partial t-trees with no large clique
Peter Bradshaw · Discrete Mathematics · 2025
Dvořák and Kawarabayashi [2] 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 ≤ ω ≤ t , then χ f ( G ) ≤ t + ω − 1 t , and we show that this bound is tight for ω = t . We also show that for each value 0 < c < 1 2 , there exists a graph G of a large treewidth t and clique number ω = ⌊ ( 1 − c ) t ⌋ satisfying χ f ( G ) ≥ t + 1 + 1 2 log ( 1 − 2 c ) + o ( 1 ) , which is approximately equal to the upper bound for small values c .