The Erds-Faber-Lovász Conjecture revisited

Abstract

The Erds-Faber-Lovász Conjecture, posed in 1972, states that if a graph is the union of cliques of order (referred to as defining -cliques) such that two cliques can share at most one vertex, then the vertices of can be properly coloured using colours. Although still open after almost 50 years, it can be easily shown that the conjecture is true when every shared vertex belongs to exactly two defining -cliques. We here provide a quick and easy algorithm to colour the vertices of in this case, and discuss connections with clique-decompositions and edge-colourings of graphs.