1-subdivisions, fractional chromatic number and Hall ratio

Zdeněk Dvořák, Patrice Ossona de Mendez, Hehui Wu

The Hall ratio of a graph G is the maximum of |V(H)|/alpha(H) over all subgraphs H of G. Clearly, the Hall ratio of a graph is a lower bound for the fractional chromatic number. It…