On Erdos-Faber-Lovasz Conjecture

Abstract

In 1972, Erdös - Faber - Lovász (EFL) conjectured that, if $\text{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=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_i:v\in V(A_i),1\le i\le n\}|$. In this paper 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 1.2 and every $A_i$ ($1\le i\le 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 1.2 and every $A_i$ ($1\le i\le n$) has at most $\lceil \frac{n+d-1}{d}\rceil$ vertices of clique degree greater than or equal to $d$ ($2\le d\le n$), then $G$ is $n$-colorable.

arXiv comment12 Pages, 6 Figures. arXiv admin note: substantial text overlap with arXiv:1508.03476