Further results on Erd?s–Faber–Lovász conjecture

Abstract

In 1972, Erd?s–Faber–Lovász (EFL) conjectured that, if (Formula presented.) is a linear hypergraph consisting of (Formula presented.) edges of cardinality (Formula presented.), then it is possible to color the vertices with (Formula presented.) 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 (Formula presented.) denote a graph with (Formula presented.) complete graphs (Formula presented.) (Formula presented.), each having exactly (Formula presented.) vertices and have the property that every pair of complete graphs has at most one common vertex, then the chromatic number of (Formula presented.) is (Formula presented.). The clique degree (Formula presented.) of a vertex (Formula presented.) in (Formula presented.) is given by (Formula presented.). In this paper we give a method for assigning colors to the graphs satisfying the hypothesis of the Erd?s–Faber–Lovász conjecture and every (Formula presented.) ((Formula presented.)) has atmost (Formula presented.) vertices of clique degree greater than one using Symmetric latin Squares and clique degrees of the vertices of (Formula presented.). © 2018 Kalasalingam University. Published with license by Taylor & Francis Group, LLC.