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 추측은 성립함을 증명하였다.

목차

요약
 Abstract
 Ⅰ. 서론
 Ⅱ. Erdős-Faber-Lova' sz 추측
 Ⅲ. 독립집합 정점 색칠 알고리즘
 Ⅳ. 실험 및 결과 분석
 Ⅴ. 결론
 References

키워드

저자

• 이상운 [ Sang-Un Lee | 정회원, 강릉원주대학교 과학기술대학 멀티미디어공학과 ] Corresponding Author

참고문헌

발행기관

간행물

표지보기 관심저널 등록

• 간행물명

  한국인터넷방송통신학회 논문지 [The Journal of the Institute of Internet, Broadcasting and Communication]

• 간기

  격월간

• pISSN

  2289-0238

• eISSN

  2289-0246

• 수록기간

  2001~2025

• 십진분류

  KDC 326 DDC 380