Fractional Aspects of the Erdős-Faber-Lovász Conjecture

Abstract

The Erdős-Faber-Lovász conjecture is the statement that every graph that is the union of n cliques of size n intersecting pairwise in at most one vertex has chromatic number n. Kahn and Seymour proved a fractional version of this conjecture, where the chromatic number is replaced by the fractional chromatic number. In this note we investigate similar fractional relaxations of the Erdős-Faber-Lovász conjecture, involving variations of the fractional chromatic number. We exhibit some relaxations that can be proved in the spirit of the Kahn-Seymour result, and others that are equivalent to the original conjecture.

Keywords

• erdős-faber-lovász conjecture
• fractional chromatic number