earticle

영어

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 k copies of k-cliques intersecting in at most one vertex pairwise is k-chromatic." i.e., x(G) = k. 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 δ(G) in the Minimum Independent Set (MIS) if both the numbers are even and to count a vertex of the maximum degree Δ(G) in otherwise. As a result of this algorithm, the number of MIS obtained is x(G) = k. When applied to Kk-clique sum intersecting graphs wherein 3 ≤ k ≤ 8 , the proposed method has proved to be successful in obtaining x(G) in all of them. To conclude, the Erdös-Faber-Lovász conjecture implying that “the k-number of Kk-clique sum intersecting graph is k-chromatic” is proven.

한국어

본 논문은 지금까지 미해결 문제로 알려진 정점 색칠 문제에 대한 Erdös-Faber-Lovász 추측을 증명하였다. Erdös-Faber-Lovász 추측은 “k개의 Kk-클릭 합 교차 그래프는 k개의 색으로 칠할 수 있다.” 즉, x(G) = k이다.” Erdös-Faber-Lovász 추측을 증명하기 위해 본 논문은 교차되는 정점수와 한 정점에서 교차되는 클릭수를 구하여 모 두 짝수이면 그래프의 최소 차수 δ(G) 정점을 최대독립집합 (minimum Independent set, MIS)에 포함시키는 방법을 적용하고, 둘 중 어느 하나가 홀수이면 최대 차수 Δ(G)정점을 MIS에 포함시키는 방법을 적용하였다. 알고리즘 수행 결과 얻은 MIS 개수가 x(G) = k이다. 3 ≤ k ≤ 8 인 Kk-클릭 합 교차 그래프에 대해 실험한 결과 모든 그래프에서 x(G) = k를 얻는데 성공하였다. 결국, “k개의 Kk-클릭 합 교차 그래프는 k개의 색으로 칠할 수 있다.”는 Erdös- Faber -Lovász 추측은 성립함을 증명하였다.