Peter Bradshaw (UIUC)
Fractional colorings of partial t-trees with no large clique*************************************************************************
Abstract: For many graph classes, a graph of maximum chromatic number must contain a large clique. Hence, when one considers only members of a graph class without a large clique, the largest attainable chromatic number is often reduced. As an example, a graph G of maximum degree d may have chromatic number d+1, but Brooks' theorem states that \chi(G) is at most d whenever G has no (d+1)-clique, and Borodin and Kostochka conjectured that \chi(G) < d whenever d > 8 and G has no d-clique.
In this talk, we consider the class of partial t-trees. A t-tree is a t-degenerate graph obtained by starting with a K_t and iteratively adding vertices v such that N(v) induces a K_t. A partial t-tree is a subgraph of a t-tree. Dvořák and Kawarabayashi (European Journal of Combinatorics, 2017) asked, what is the largest chromatic number attainable by a partial t-tree with no K_r subgraph? In this talk, we consider the fractional version of this question. We prove that if G is a partial t-tree with clique number (1-c)t for c < 1, then the fractional chromatic number of G is at most t + 1 - c. We also show that for c < 1/2, there exists a partial t-tree G with clique number (1 - c)t with fractional chromatic number at least t + 1 + log(1-2c) + o(1).
