2015/08/14 by H., Suresh M., Dara, V. V. P. R. V. B. Suresh · 1 citation
#05A05 #05B15 #05C15 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1508.03476
In 1972, Erdös - Faber - Lovász (EFL) conjectured that, if H is a linear hypergraph consisting of n edges of cardinality n, then it is possible to color the vertices with n colors so that no two vertices with the same color are in the same edge. In 1978, Deza, Erdös and Frankl had given an equivalent version of the same for graphs: Let G= \bigcup i=1n Ai denote a graph with n complete graphs A1, A2, … , An, each having exactly n vertices and have the property that every pair of complete graphs has at most one common vertex, then the chromatic number of G is n. The clique degree dK(v) of a vertex v in G is given by dK(v) = |\Ai: v ∈ V(Ai), 1 ≤ i ≤ n\|. In this paper we give an algorithmic proof of the conjecture using the symmetric latin squares and clique degrees of the vertices of G.