SJIF(2020): 5.702

International Journal of Advanced Research and Publications

High Quality Publications & World Wide Indexing!

Erdos - Faber - Lovasz Graphs

Volume 1 - Issue 3, September 2017 Edition
[Download Full Paper]

Oreste M. Ortega Jr.
bridge point, component-bridge point transformation, decomposable graph, Erdös-Faber-Lovasz graph
A famous conjecture of Erdös, Faber, and Lovasz states that if the edge set of a graph G can be covered with n copies of Kn, the complete graph on n vertices, such that two of this Kn share at most one vertex, then the chromatic number (G) of G is just n. The best upper bound so far has been proved by W. I. Chang and E. Lawler in [2]. A graph G is said to be decomposable into subgraphs G1, G2, … , Gk if any two subgraphs Gi and Gj have no edges in common and the union of all subgraphs Gi, 1 ≤ i ≤ k, is G. We say that graph G is an Erdös-Faber-Lovasz graph (EFL) if G is decomposable into k complete graphs on k vertices. That is, G= ∪_(i=1)^k G_i where each Gi is a complete graph with k vertices. We call each Gi the summand of G. If G is an EFL graph then it follows from the definition of a decomposable graph that every pair (Gi,Gj) of G has at most one common vertex. We say that a vertex v of G a bridge point if there exist Gi and Gj such that v ϵ V(G_i )∩V(G_j).
[1]. Bondy, J. A. and U. S. R. Murty, “Graph Theory”. Springer 2008

[2]. Chang, W. I. and E. Lawler, “Edge Coloring on Hypergraphs and Conjecture of Erdös, Faber, Lovasz”, Combinatorica 8, pp. 293 – 295, 1988

[3]. Erdös, Paul, “On the combinatorial problems which I most like to see solved.”, Combinatorica 1, pp. 25 – 42, 1981

[4]. Horak, Peter, “A Coloring Problem Related to the Erdös-Faber-Lovasz Conjecture.”, Journal of Combinatorial Theory, Series B 50, 323, pp. 321 – 322, 1990.