Proof Algorithm of Erdös-Faber-Lovász Conjecture
Sang-Un Lee · 한국인터넷방송통신학회 논문지 · 2015
Abstract This paper proves Erdos-Faber-Lovasz conjecture of vertex coloring problem, which is so far unresolved. The Erdos-Faber-Lovasz 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 number of intersecting vertices and that of cliques that intersect at one vertex so as to count a vertex of minimum degree in Minimum Independent Set (MIS) if both numbers are even and to count a vertex of maximum degree in otherwise. As a result of this algorithm, number of MIS obtained is . When applied to -clique sum intersecting graphs wherein ≤≤ , proposed method has proved to be successful in obtaining in all of them. To conclude, Erdos-Faber-Lovasz conjecture implying that “the -number of -clique sum intersecting graph is k-chromatic” is proven.