Estimating the fractional chromatic number of a graph

Abstract

The fractional chromatic number of a graph is defined as the optimum of a rather unwieldy linear program. (Setting up the program requires generating all independent sets of the given graph.) Using combinatorial arguments we construct a more manageable linear program whose optimum value provides an upper estimate for the fractional chromatic number. In order to assess the feasibility of the proposal and in order to check the accuracy of the estimates we carry out numerical experiments.

Keywords

• clique and chromatic numbers
• fractional chromatic number
• integer programming
• 11a05
• 11r04