Proof Algorithm of Erdös-Faber-Lovász ConjectureJournal: The Journal of the Institute of Internet, Broadcasting and Communication (Vol.15, No. 1)
Publication Date: 2015-02-28
Authors : Sang-Un; Lee;
Page : 269-276
Keywords : Vertex chromatic number; Maximum Degree; Minimum degree; -clique sum intersecting graph;
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.
Other Latest Articles
Last modified: 2015-11-18 17:12:21