Abstract :

In 1972, Erdos - Faber - Lovasz (EFL) conjectured that, if $ extbf{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, Erdos and Frankl had given an equivalent version of the same for graphsLet $G= igcup _{i=1}^{n} A_i$ denote a graph with $n$ complete graphs $A_1, A_2,$ $ dots , A_n$, 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 $d^K(v)$ of a vertex $v$ in $G$ is given by $d^K(v) = |{A_iv in V(A_i), 1 leq i leq n}|$. In this presentation we give a method for assigning colors to the graphs satisfying the hypothesis of the Erdös - Faber - Lovász conjecture using intersection matrix of the cliques $A_i$'s of $G$ and clique degrees of the vertices of $G$. Also, we give theoretical proof of the conjecture for some class of graphs. In particular we show that: 1. If $G$ is a graph satisfying the hypothesis of the Conjecture and every $A_i$ ($1 leq i leq n$) has at most $sqrt{n}$ vertices of clique degree greater than 1, then $G$ is $n$-colorable. 2. If $G$ is a graph satisfying the hypothesis of the Conjecture and every $A_i$ ($1 leq i leq n$) has at most $left lceil {frac{n+d-1}{d}} ight ceil$ vertices of clique degree greater than or equal to $d$ ($2leq d leq n$), then $G$ is $n$-colorable.