Головна |
У 1943 р Г. Хадвігера висунув гіпотезу, тісно пов'язану з проблемою чотирьох фарб.
Гіпотеза Хадвігера а. Будь-зв'язний п-хроматичний граф стягаємо до До4.
для п ? 4 гіпотеза підтверджується. Справді, при п = 1 твердження тривіально. при п = 2 кожен зв'язний граф стягується до ребру, а при п = 3 - містить цикл і тому стягується до К3 . Наступна теорема доводить гіпотезу для п = 4.
Теорема 60.1. Кожен зв'язний n-хроматичний граф стягаємо до До4 .
нехай G - Зв'язний 4-хроматичний граф. Якщо в G є точки зчленування, то деякий його блок повинен бути 4-хроматичним, інакше з теореми 53.3 слід було б, що ? (G) < 4. стягніть G до цього блоку. З тієї ж причини блок залишиться 4-хроматичним після стягування ребер, інцидентних вершині ступеня 2. Таким чином, не втрачаючи спільності, можна вважати G блоком зі ступенями вершин не менше трьох.
нехай C = (v1, v2 , ..., Vp , v1) - простий цикл максимальної довжини р в G. Очевидно, що р ? 4. Просту ланцюг, що зв'язує дві несоседних вершини циклу С і не містить інших вершин цього циклу, назвемо З-хордою. Покажемо, що для будь-якої вершини v1 циклу С існує С-хорда, якій належить ця вершина. Так як deg v1 ? 3, То є ребро е = v1u, що не належить С. Якщо и € VC, то ребро е є С-хордою. нехай u ? VC. Тоді по теоремі 34.1 існує простий цикл Ci = (v1, u2 , ..., V2 , ..., V1),що містить ребро е и
вершину v2. ланцюг L = (v1, І, ..., v2) Повинна мати деяку вершину vi відмінну від v2 і належить циклу З, інакше С не був би простим циклом максимальної довжини. частина ланцюга L від v1 до першої вершини, що належить циклу З, і буде шуканої З-хордою.
Припустимо, що існують дві С-хорди Т1 = (vi, ..., vj) и T2 = (vk , ..., Vl) із загальною вершиною t поза С. Тоді частина графа, що складається з С, Т1 и T2, Стягується до К4. Один з варіантів стягування зображений на рис. 60.1, а.
Тепер розглянемо випадок, коли не існує пересічних С-хорд. Будь-яка С-хорда ділить цикл С на дві прості ланцюга. Виберемо таку З-хорду Т1, щоб одна з цих ланцюгів З '= (vi , ...,vj) була найкоротшою, і візьмемо вершину vh на цьому ланцюзі (така вершина існує, оскільки С-хорда з'єднує дві несоседних вершини циклу). Розглянемо деяку З-хорду Т2 = (vk, ..., vi). Якщо при цьому вершина vi буде розташована на З ', то ланцюг (vk,..., vi), що належить циклу С, Буде коротше, ніж З '. отже, vi не лежить на ланцюгу С У цьому випадку частина графа, що складається з С, Т1 и Т2, Стягується до К4. Один з варіантів стягування показаний на рис. 60.1, б.
Після тогокак буде отримано граф К4 решту вихідного графа стягнемо до К4.
Відомо, що твердження гіпотези Хадвігера при n = 5 еквівалентно гіпотезі чотирьох фарб. А саме, вірна наступна
Теорема 60.2. Наступні два твердження еквівалентні:
1) гіпотеза чотирьох фарб вірна;
2) будь-який зв'язний 5-хроматичний граф стягаємо до К5.
На закінчення цього параграфа розглянемо один алгебраїчний підхід до проблеми розмальовки плоских графів. Детально про це див. [14].
нехай тепер G - Довільний зв'язний граф, кожному ребру vivj якого поставлена ??у відповідність змінна yij. Отримаємо систему рівнянь S (G), записавши зоотношенія виду (1) для кожного циклу графа G, і сі-угему S (G)-для кожного циклу з деякого фіксованого базису циклів.
Лемма 60.3. Кожному рішенню системи S (G) при фіксованій забарвленні ?(v0) деякої вершини v0 однозначно відповідає правильна розфарбування графа G чотирма кольорами.
де yij складають рішення системи S (G).
В силу (1) значення ? {v?) не залежить від вибору ланцюга Р?, тому воно визначає колір вершини v?. Так як yij ? 0 для vivj € EG, то будь-які суміжні вершини сміють різні кольори. Таким чином, розфарбування, що задається формулою (2), правильна.
Так як граф може містити велику кількість циклів, то перейдемо від системи рівнянь S (G) до системи S (G).
Теорема 60.4. Кожному рішенню системи S (G) при фіксованій забарвленні ? (v0) Деякої вершини v0 однозначно відповідає правильна розфарбування графа G чотирма кольорами.
що не належить базису циклів З ' графа G. Відомо (§ 21), що С можна представити у вигляді суми по модулю 2 декількох циклів з С. нехай С = С1 + С2,
Аналогічні міркування можна привести і в тому випадку, коли цикл С є сумою не двох, а більшого числа циклів з базису циклів З '. Значить, співвідношення (1) виконується для будь-якого простого циклу. Якщо ж цикл С не простий, то необхідно представити його у вигляді об'єднання декількох простих циклів, для кожного з яких виконується (1).
Проблема чотирьох фарб | вчинені графи
правильна розфарбування | Оцінки хроматичного числа | розфарбування ребер | Зв'язок матроідних розкладів графів з розмальовками | Тріангулірованние графи |