Erdos - Faber - Lovasz Graphs

A famous conjecture of Erds Faber and Lovasz states that if the edge set of a graph G can be covered with n copies of Kn the complete graph on n vertices such that two of this Kn share at most one vertex then the chromatic number G of G is just n. The best upper bound so far has been proved by W. I. Chang and E. Lawler in 2. A graph G is said to be decomposable into subgraphs G1 G2 Gk if any two subgraphs Gi and Gj have no edges in common and the union of all subgraphs Gi 1 i k is G. We say that graph G is an Erds-Faber-Lovasz graph EFL if G is decomposable into k complete graphs on k vertices. That is G i1k Gi where each Gi is a complete graph with k vertices. We call each Gi the summand of G. If G is an EFL graph then it follows from the definition of a decomposable graph that every pair GiGj of G has at most one common vertex. We say that a vertex v of G a bridge point if there exist Gi and Gj such that v VGi VGj.