Some Results on the Erdős–Faber–Lovász Conjecture

Abstract

Erdős–Faber–Lovász conjecture states that if a graph G is a union of the n edge-disjoint copies of complete graph Kn, that is, each pair of complete graphs has at most one shared vertex, then the chromatic number of graph G is n. In fact, we only need to consider the graphs where each pair of complete graphs has exactly one shared vertex. However, each shared vertex may be shared by more than two complete graphs. Therefore, this paper first considers the graphs where each shared vertex happens to be shared by two complete graphs, and then discusses the graphs with only one shared vertex shared by more than two complete graphs. The conjecture is correct for these two kinds of graphs in this work. Finally, the graph where each shared vertex happens to be shared by three complete graphs has been studied, and the conjecture also holds for such graphs when n=13. The graphs discussed in this paper have certain symmetric properties. The symmetry of graphs plays an important role in coloring. This work is an attempt to combine the symmetry of graphs with the coloring of graphs.

Keywords

• Erdős–Faber–Lovász conjecture
• complete graph
• shared vertex
• hypergraph
• coloring