On a fractional version of Haemers' bound

Research paper by Boris Bukh, Christopher Cox

Indexed on: 01 Feb '18Published on: 01 Feb '18Published in: arXiv - Computer Science - Information Theory

Abstract

In this note, we present a fractional version of Haemers' bound on the Shannon capacity of a graph, which is originally due to Blasiak. This bound is a common strengthening of both Haemers' bound and the fractional chromatic number of a graph. We show that this fractional version outperforms any bound on the Shannon capacity that could be attained through Haemers' bound. We show also that this bound is multiplicative, unlike Haemers' bound.