Хроматичної число - студопедія

Гіпотезу чотирьох фарб можна з повним правом назвати ще «хворобою чотирьох фарб», так як вона багато в чому схожа на захворювання. Вона надзвичайно заразна. Іноді вона протікає порівняно легко, але в деяких випадках, набуває затяжного або навіть загрозливого характеру. Ніяких щеплень проти неї не існує; правда, люди з досить здоровим організмом після короткої спалаху набувають довічний імунітет. На цю недугу людина може хворіти кілька разів, і вона часом супроводжується гострим болем, але жодного летального результату зареєстровано не було. Відомий, принаймні один випадок передачі хвороби від батька до сина, так що, може бути, вона спадкова.

Проте, саме спроби обгрунтувати цю гіпотезу стимулювали отримання ряду результатів по розмальовці графів, які в свою чергу привели до досліджень деяких інших розділів теорії графів.

В цьому розділі після визначення розмальовки графа і його хроматичного числа викладається доказ теореми про п'ять фарбах, а потім обговорюється гіпотеза чотирьох фарб. Далі вводяться однозначно розфарбовувати графи, т. Е. Графи, які можна розфарбувати єдиним чином, а також критичні графи (мінімальні щодо розмальовки). Досліджується тісний взаємозв'язок між гомоморфізми і розмальовками. Глава завершується описом властивостей хроматичного многочлена.

Розфарбуванням графа називається таке приписування квітів його вершин, що ніякі дві суміжні вершини не отримують однакового кольору. Безліч всіх вершин одного кольору є незалежним і називається одноколірним класом. В n-розмальовці графа G використовується n кольорів, таким чином, це розфарбування розбиває V на n одноколірних класів. Хроматичної число хr (G) графа G визначається як найменше n, для якого граф G має n-розмальовку. Граф G називається n-розфарбовуваним, якщо хr (G)

Оскільки граф G, очевидно, має n-розмальовку і хr (G) -розмальовка, він повинен мати також n-розмальовку для будь-якого п, що задовольняє нерівностям хr (G)

Легко знайти хроматичні числа деяких відомих графів:

xr (КР) = Р, хr (Кр-х) = р-1, хr (! Кр) = 1, хr (Кm, n) = 2, хr (С2n) = 2, xr (C2n + i) = 3 і хr (Т) = 2 для будь-якого нетривіального дерева Т.

Очевидно, що граф є 1-хроматичним тоді і тільки тоді, коли він цілком незв'язний. Опис двоцвітних (2-розфарбовувати) графів дано Кенігом і відображено в теоремі

Теорема.Граф двуцветен тоді і тільки тоді, коли він не містить непарних простих циклів.

Схоже, що проблема характеризації n-кольорових графів для n> 3 все ще не вирішена, оскільки такий критерій навіть дляn = 3 допоміг би вирішити гіпотезу чотирьох фарб. Не знайдені також ефективні методи визначення хроматичного числа довільного графа. Однак відомо кілька оцінок для xr (G), в яких використовуються різні інші інваріанти. Одна очевидна нижня оцінка - це число вершин в повному найбільшому підграфі графа G. Ми розглянемо зараз верхні оцінки; перша така оцінка була отримана Секерешем і Вілф

Теорема. Для будь-якого графа G хr (С)<1+mахd(С'),где максимум берется по всем порожденным подграфам G' графа G.

Слідство е (а). Для будь-якого графа G хроматичної число не більше ніж на 1 перевищує максимальну ступінь:

Брукс показав, проте, що часто цю оцінку можна поліпшити.

Теорема. ЕсліD (G) = n, то граф G завжди n-розфарбовуємо, за винятком наступних двох випадків:

1) n = 2 і G має компоненту, що є непарних циклом ',

2) n> 2 і Кn + 1 компонента графа G.

Досліджуючи наведені вище міркування, легко перейнятися вірою в те, що всі графи з великим хроматичним числом мають великі кліки і, отже, містять трикутники. І ось Дірак поставив питання, чи існує граф без трикутників, але з довільно великим хроматичним числом. Позитивно на це питання відповіли незалежно один від одного Бланш Декарт, Зиков і Мицельскій. Потім їх результат узагальнили Дж. І Л. Келлі. довівши, що для будь-якого п> 2 існує n-хроматичний граф, обхват якого перевершує 5. Вони припустили, що справедливо наступне твердження, яке першим довів Ердеш. використовуючи імовірнісні міркування. Пізніше Ловац дав конструктивне доведення цієї теореми.

Теорема. Для будь-яких двох позитивних цілих чисел t і n існує n-хроматичний граф, обхват якого перевершує t.