Кіріспе
Графтардың беттеріндегі түстің тағайындалуы туралы теорема
In graph theory, the Heawood conjecture or Ringel–Youngs theorem gives a lower bound for the number of colors that are necessary for graph coloring on a surface of a given genus. For surfaces of genus 0, 1, 2, 3, 4, 5, 6, 7, , the required number of colors is 4, 7, 8, 9, 10, 11, 12, 12, , the chromatic number or Heawood number. The conjecture was formulated in 1890 by P. J. Heawood and proven in 1968 by Gerhard Ringel and J. W. T. Youngs. One case, the non orientable Klein bottle, proved an exception to the general formula. An entirely different approach was needed for the much older problem of finding the number of colors needed for the plane or sphere, solved in 1976 as the four color theorem by Haken and Appel. On the sphere the lower bound is easy, whereas for higher genera the upper bound is easy and was proved in Heawood's original short paper that contained the conjecture. In other words, Ringel, Youngs, and others had to construct extreme examples for every genus g = 1, 2, 3, If g = 12s + k, then the genera fall into the 12 cases as k = 0, 1, 2, 3, ., 11. To simplify, suppose that case k has been established if only a finite number of gs of the form 12s + k are in doubt. Then the years in which the twelve cases were settled, and by whom, are the following:
1954, Ringel: case 5
1961, Ringel: cases 3, 7, 10
1963, Terry, Welch, Youngs: cases 0, 4
1964, Gustin, Youngs: case 1
1965, Gustin: case 9
1966, Youngs: case 6
1967, Ringel, Youngs: cases 2, 8, 11
The last seven sporadic exceptions were settled as follows:
1967, Mayer: cases 18, 20, 23
1968, Ringel, Youngs: cases 30, 35, 47, 59, and the conjecture was proved.
Графтар теориясында Хьювудтың болжамы немесе Рингель-Юнгс теоремасы, берілген туысқандыққа ие бетте графтарды түстің тағайындалуы үшін қажетті түстердің ең төменгі шегін көрсетеді. 0, 1, 2, 3, 4, 5, 6, 7, … туысқандығы бар беттер үшін қажетті түстердің саны 4, 7, 8, 9, 10, 11, 12, … хроматикалық сан немесе Хьювуд саны болып табылады. Бұл болжамды 1890 жылы П.Ж. Хьювуд ұсынған, ал 1968 жылы Герхард Рингель мен Дж.У.Т. Юнгс дәлелдеген. Бір жағдай, бағытталмаған Клайн бөтелкесі, жалпы формуладан өзгешелік құрады. 1976 жылы Хакен мен Апель төрт түстің теоремасы ретінде шешкен жазықтық немесе сфера үшін қажетті түстердің санын табу мәселесіне мүлдем басқа тәсіл қажет болды. Сферада ең төменгі шек анықталған, ал жоғары туысқандықтар үшін ең жоғарғы шек анықталған және Хьювудтың болжамын қамтитын бастапқы қысқа мақаласында дәлелденген. Басқаша айтқанда, Рингель, Юнгс және басқалар әрбір туысқандық үшін g = 1, 2, 3, … экстремалды мысалдар құрастыруға мәжбүр болды. Егер g = 12s + k болса, онда туысқандықтар 12 жағдайға бөлінеді: k = 0, 1, 2, 3, …, 11. Жеңілдету үшін, егер 12s + k түріндегі g-лардың тек шектеулі саны күмәнді болса, k жағдайы анықталды деп есептеңіз. Содан кейін он екі жағдайды шешкен жылдар мен авторлар: 1954, Рингель: 5 жағдай 1961, Рингель: 3, 7, 10 жағдай 1963, Терри, Уэлч, Юнгс: 0, 4 жағдай 1964, Густин, Юнгс: 1 жағдай 1965, Густин: 9 жағдай 1966, Юнгс: 6 жағдай 1967, Рингель, Юнгс: 2, 8, 11 жағдай. Соңғы жеті сирек кездесетін өзгешеліктер келесідей шешілді: 1967, Майер: 18, 20, 23 жағдай 1968, Рингель, Юнгс: 30, 35, 47, 59 жағдай, және болжам дәлелденді.
In graph theory, the Heawood conjecture or Ringel–Youngs theorem gives a lower bound for the number of colors that are necessary for graph coloring on a surface of a given genus. For surfaces of genus 0, 1, 2, 3, 4, 5, 6, 7, , the required number of colors is 4, 7, 8, 9, 10, 11, 12, 12, , the chromatic number or Heawood number. The conjecture was formulated in 1890 by P. J. Heawood and proven in 1968 by Gerhard Ringel and J. W. T. Youngs. One case, the non orientable Klein bottle, proved an exception to the general formula. An entirely different approach was needed for the much older problem of finding the number of colors needed for the plane or sphere, solved in 1976 as the four color theorem by Haken and Appel. On the sphere the lower bound is easy, whereas for higher genera the upper bound is easy and was proved in Heawood's original short paper that contained the conjecture. In other words, Ringel, Youngs, and others had to construct extreme examples for every genus g = 1, 2, 3, If g = 12s + k, then the genera fall into the 12 cases as k = 0, 1, 2, 3, ., 11. To simplify, suppose that case k has been established if only a finite number of gs of the form 12s + k are in doubt. Then the years in which the twelve cases were settled, and by whom, are the following:
1954, Ringel: case 5
1961, Ringel: cases 3, 7, 10
1963, Terry, Welch, Youngs: cases 0, 4
1964, Gustin, Youngs: case 1
1965, Gustin: case 9
1966, Youngs: case 6
1967, Ringel, Youngs: cases 2, 8, 11
The last seven sporadic exceptions were settled as follows:
1967, Mayer: cases 18, 20, 23
1968, Ringel, Youngs: cases 30, 35, 47, 59, and the conjecture was proved.
Мысал
Торостың g = 1 болса, χ = 0 болады. Сондықтан, формула көрсеткендей, торды кез келген аймақтарға бөлуге ең көп жеті түс қолданып бояуға болады. Суретте тордың жеті аймаққа бөлінуі көрсетілген, мұнда әр аймақ қалған барлық аймақтармен іргелес жатыр; бұл бөлініс осы жағдайда түстер санының жетіге дейінгі шегінің қатаң екенін көрсетеді. Бұл бөліністің шекарасы Хьювуд графигінің торусқа орналасуын құрайды.