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 . 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).
. Bondy, J. A. and U. S. R. Murty, â€œGraph Theoryâ€. Springer 2008
. Chang, W. I. and E. Lawler, â€œEdge Coloring on Hypergraphs and Conjecture of ErdÃ¶s, Faber, Lovaszâ€, Combinatorica 8, pp. 293 â€“ 295, 1988
. ErdÃ¶s, Paul, â€œOn the combinatorial problems which I most like to see solved.â€, Combinatorica 1, pp. 25 â€“ 42, 1981
. 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.