2017/01/17 by S. M. Hegde, Hegde, S. M., Suresh Dara +1
Computer Science · Engineering · Mathematics · #05A05 #05B15 #05C15 #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1701.04550
openalex publication_date 2017/01/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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= \bigcupi=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 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 Ai'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 Ai (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 1.2 and every Ai (1 ≤ i ≤ n) has at most \lceil (n+d-1)/(d) \rceil vertices of clique degree greater than or equal to d (2≤ d ≤ n), then G is n-colorable.