ResearchBib Share Your Research, Maximize Your Social Impacts
Sign for Notice Everyday Sign up >> Login

Proof Algorithm of Erdös-Faber-Lovász Conjecture

Journal: The Journal of the Institute of Internet, Broadcasting and Communication (Vol.15, No. 1)

Publication Date:

Authors : ; ;

Page : 269-276

Keywords : Vertex chromatic number; Maximum Degree; Minimum degree; -clique sum intersecting graph;

Source : Downloadexternal Find it from : Google Scholarexternal


This paper proves the Erdös-Faber-Lovász conjecture of the vertex coloring problem, which is so far unresolved. The Erdös-Faber-Lovász conjecture states that "the union of copies of -cliques intersecting in at most one vertex pairwise is -chromatic." i.e., . In a bid to prove this conjecture, this paper employs a method in which it determines the number of intersecting vertices and that of cliques that intersect at one vertex so as to count a vertex of the minimum degree in the Minimum Independent Set (MIS) if both the numbers are even and to count a vertex of the maximum degree in otherwise. As a result of this algorithm, the number of MIS obtained is . When applied to -clique sum intersecting graphs wherein , the proposed method has proved to be successful in obtaining in all of them. To conclude, the Erdös-Faber-Lovász conjecture implying that “the -number of -clique sum intersecting graph is k-chromatic” is proven.

Last modified: 2015-11-18 17:12:21