Room 327

Erdos-Faber-Lovasz Conjecture

Suresh Dara

IMSc

In 1972, Erd ̈s - Faber - Lovasz (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, Erdos and Frankl had given an equivalent version of
the same for graphs: Let G = ni=1 A i denote a graph with n complete graphs
A 1 , A 2 , . . . , 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 ∈
V (A i ), 1 ≤ i ≤ n}|. In this presentation we give a method for assigning colors
to the graphs satisfying the hypothesis of the Erds - Faber - Lovsz 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 ≤ i ≤ n) has at most 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


vertices of clique degree greater than or
(1 ≤ i ≤ n) has at most n+d−1
d
equal to d (2 ≤ d ≤ n), then G is n-colorable.