지원사업
학술연구/단체지원/교육 등 연구자 활동을 지속하도록 DBpia가 지원하고 있어요.
커뮤니티
연구자들이 자신의 연구와 전문성을 널리 알리고, 새로운 협력의 기회를 만들 수 있는 네트워킹 공간이에요.
논문 기본 정보
- 자료유형
- 학술저널
- 저자정보
- 발행연도
- 2014.5
- 수록면
- 19 - 25 (7page)
이용수
초록· 키워드
오류제보하기
본 논문은 평면상의 거리가 1인 인접 정점들에 대해 서로 다른 색을 칠할 경우 최대로 필요한 색인 채색수를 찾는 문제를 연구하였다. 지금까지 채색수 상한 값은 4≤χ(G)≤7로 알려져 있으며, Hadwiger-Nelson은 χ(G)≤7, Soifer는 χ(G)≤9를 제안하였다. 먼저, 최소로 필요로 하는 채색수를 구하는 알고리즘을 제안하고, Hadwiger-Nelson의 정육각형 그래프를 대상으로 채색수를 구한 결과 χ(G)=3이 될 수 있음을 보였다. Hadwiger-Nelson의 정육각형 그래프를 12개 인접 정점으로 가정할 경우 χ(G)=4를 구하였다. 또한, Soifer의 8개 인접 정점 정사각형 그래프에 대해 채색수를 구한 결과 χ(G)=4임을 보였다. 결국, 제안된 알고리즘은 최소 차수 정점부터 색을 배정하는 단순한 다항시간 규칙을 적용하여 평면의 최대 채색수는 χ(G)=4임을 제안한다.
목차
등록된 정보가 없습니다.
참고문헌 (17)
참고문헌 신청
1. [학술지(정기간행물)] - T. R. Jensen / 2001 / 25 Pretty Graph Colouring Problems / Discrete Mathematics 299 (1-3) : 167 ~ 169
2. [인터넷자원] - Wikipedia / / Hadwiger-Nelson Problem
3. [인터넷자원] - E. W. Weisstein / / Hadwiger-Nelson Problem
4. [학술지(정기간행물)] - G. Exoo / 2005 / Epsilon Unit Distance Graphs / Discrete and Computational Geometry 33 (1) : 117 ~ 124
5. [학위논문] - M. Payne / 2007 / Unit Distance Colouring Problems / Monash University
2. [인터넷자원] - Wikipedia / / Hadwiger-Nelson Problem
3. [인터넷자원] - E. W. Weisstein / / Hadwiger-Nelson Problem
4. [학술지(정기간행물)] - G. Exoo / 2005 / Epsilon Unit Distance Graphs / Discrete and Computational Geometry 33 (1) : 117 ~ 124
5. [학위논문] - M. Payne / 2007 / Unit Distance Colouring Problems / Monash University
이 논문의 저자 정보
이 논문과 함께 이용한 논문
최근 본 자료
댓글(0)
0