희우드 추측

그래프 이론에서, 히우드 추측이나 링겔-영스 정리는 주어진 속 표면의 그래프 색소에 필요한 색의 수에 대한 하한을 부여한다.속 0, 1, 2, 3, 4, 5, 6, 7, ...의 표면의 경우 필요한 색상 수는 4, 7, 8, 9, 10, 11, 12, 12, ....OEIS: A000934, 색수 또는 Heawood 수이다.

이 추측은 1890년 퍼시 존 헤이워드에 의해 공식화되었고 1968년 게르하르트 링겔과 테드 영스에 의해 증명되었다.한 가지 경우, 방향성이 맞지 않는 클라인 병은 일반 공식의 예외임을 증명했다.1976년 하켄과 아펠에 의한 4색 정리로서 해결된 평면이나 구체에 필요한 색의 수를 찾는 훨씬 오래된 문제에 대해서는 전혀 다른 접근법이 필요했다.구체에서는 하한이 쉬운 반면, 상위 세대에 대해서는 상한이 쉽고 추측을 담고 있는 헤이워드의 원래 짧은 논문에서 증명되었다.즉 링겔, 영스 등은 모든 속(g = 1,2,3,....)에 대해 극단적인 예를 구성해야 했다.g = 12s + k일 경우 genera는 k = 0,1,2,3,4,5,6,7,8,9,10,11에 따라 12개의 경우에 해당된다.단순화하기 위해 12s + k 형식의 g's 한정된 수만이 의심스러운 경우 사례 k가 설정되었다고 가정한다.그 다음에 12건의 사건이 해결된 연도는 다음과 같다.

• 1954년, 링겔: 사례 5
• 1961년, 링겔: 사례 3,7,10
• 1963년, 테리, 웰치, 영즈: 케이스 0,4
• 1964년, 구스틴, 영즈: 사례 1
• 1965년, 구스틴: 사례 9
• 1966, 영즈: 사례 6
• 1967, 링겔, 영즈: 케이스 2,8,11

마지막 산발적 예외 7건은 다음과 같이 해결되었다.

• 1967년, 메이어: 사례 18, 20, 23
• 1968년, 링겔, 영즈: 사례 30, 35, 47, 59, 추측이 증명되었다.

형식명세서

1890년 Percy John Heawood는 특정 속 g > 0에 대해 해당 속(또는 표면의 어떤 분할 영역을 단순히 연결된 영역으로 색칠하는 데 동등하게)의 방향성 표면에 그려진 모든 그래프를 색칠하는 데 필요한 최소 색의 수가 다음과 같이 제공된다고 추측했다.

${\displaystyle \cHB=\좌측\lfloor {7+{\sqrt{1+48g}}{2}}:\우측\철근,}$

여기서 $\lfloor {\displaystyle }$ ${\displaystyle x}$ ${\displaystyle \rfloor }$ ${\$은(는) 바닥 기능이다.

속들을 오일러 특성에 의해 대체함으로써, 우리는 방향성 있는 경우와 방향성이 없는 경우를 모두 포함하는 공식을 얻는다.

${\displaystyle \chi )=\좌측\lfloor {7+{\\sqrt{49-24\}}{2}}:\오른쪽\철저한 .}$

이러한 관계는 링겔과 영스가 보여준 바와 같이 클라인 병을 제외한 모든 표면에서 유지된다.필립 프랭클린(1930)은 클라인 병이 공식으로 예측한 7가지 색상이 아닌 최대 6가지 색상을 요구한다는 것을 증명했다.프랭클린 그래프는 6개의 상호 인접 지역을 형성하는 방식으로 클라인 병에 그려질 수 있어 이 바운드가 단단하다는 것을 보여준다.

헤이워드의 원래 짧은 논문에서 증명된 상한선은 탐욕스러운 색칠 알고리즘에 기초한다.오일러 특성을 조작함으로써 주어진 표면에 내장된 모든 그래프는 주어진 한계보다 최소 한 개의 정도 정점을 가져야 함을 보여줄 수 있다.이 정점을 제거하고 그래프의 나머지 부분에 색상을 입힌다면, 제거된 정점에 입사하는 적은 수의 가장자리가 바운드 이상으로 필요한 색상 수를 늘리지 않고 그래프에 다시 추가되고 색상을 입힐 수 있다.다른 방향에서는 증거가 더 어렵고, 각각의 경우(클라인 병을 제외)에서 주어진 색상 수와 동일한 정점 수를 가진 완전한 그래프를 표면에 삽입할 수 있다는 것을 보여주는 것을 포함한다.

예

토러스에는 g = 1이 있으므로 χ = 0이 있다.따라서 공식에서 알 수 있듯이, 토러스를 영역으로 분할하는 것은 최대 7가지 색상을 사용하여 색칠할 수 있다.그림에는 7개 지역이 서로 인접해 있는 토러스 구획이 표시된다. 이 구획은 색상 수에 대한 7개 구획이 엄격한 것을 보여준다.이 구획의 경계는 히우드 그래프를 토러스 위에 내장하고 있다.

참조

• Franklin, P. (1934). "A six color problem". MIT Journal of Mathematics and Physics. 13 (1–4): 363–379. doi:10.1002/sapm1934131363. hdl:2027/mdp.39015019892200.
• Heawood, P. J. (1890). "Map colour theorem". Quarterly Journal of Mathematics. 24: 332–338.
• Ringel, G.; Youngs, J. W. T. (1968). "Solution of the Heawood map-coloring problem". Proceedings of the National Academy of Sciences of the United States of America. 60 (2): 438–445. Bibcode:1968PNAS...60..438R. doi:10.1073/pnas.60.2.438. MR 0228378. PMC 225066. PMID 16591648.

외부 링크

• Weisstein, Eric W. "Heawood Conjecture". MathWorld.