Критичний граф
Критичний граф — граф, у якому видалення будь-якої вершини або ребра призводить до зменшення хроматичного числа графу.
Пов'язані визначення
- -критичний граф — це критичний граф із хроматичним числом k.
- Граф G з хроматичним числом k є вершинно-k-критичним, якщо кожна з його вершин є критичним елементом[1].
Властивості
- Нехай G є k-критичним графом із n вершинами і m ребрами. Тоді:
- G має тільки одну компоненту.
- G — скінченний (теорема де Брёйна — Ердеша Шаблон:Sfn).
- δ(G) ≥ k − 1, тобто будь-яка вершина суміжна щонайменше k − 1 іншим вершинам. Строгіше, G реберно (k − 1)-зв'язнийШаблон:Sfn.
- Якщо граф G (k − 1)-регулярний (кожна вершина суміжна рівно k − 1 іншим), то граф G або є повним графом Kk, або непарним циклом (теорема БруксаШаблон:Sfn).
- 2m ≥ (k − 1)n + k − 3Шаблон:Sfn.
- 2m ≥ (k − 1)n + [(k − 3)/(k2 − 3)]nШаблон:Sfn.
- Або G можна розбити на два менших критичних графи з ребром між кожною парою вершин, де дві вершини беруться з різних частин, або граф G має щонайменше 2k − 1 вершинШаблон:Sfn. Строгіше, або G має розклад такого типу, або для кожної вершини v графу G існує k-розфарбування, в якому v є єдиною вершиною зі своїм кольором, а всі інші класи кольорів мають щонайменше дві вершиниШаблон:Sfn.
- Граф G є вершинно-критичним тоді і тільки тоді, коли для будь-якої вершини v існує оптимальне підхоже розфарбування, в якому вершина v одна представляє клас кольору.
- 1-критичних графів не існує.
- Єдиний 2-критичний граф — це K2.
- Всі 3-критичні графи вичерпуються простими циклами непарної довжиниШаблон:Sfn.
- Як показав ХайошШаблон:Sfn, будь-який k-критичний граф можна сформувати з повного графу Kk комбінацією Шаблон:Нп з операцією ототожнення двох несуміжних вершин. Граф, утворений таким способом, завжди вимагає k кольорів у будь-якому правильному розфарбуванні.
- Хоча кожен реберно-критичний граф обов'язково є критичним, зворотне хибне. Наприклад, граф наведений праворуч, є 4-критичним, але не реберно-критичнимШаблон:Sfn.
Варіації та узагальнення
- Двічі критичний граф — це зв'язний граф, у якому видалення будь-якої пари суміжних вершин зменшує хроматичне число на 2. Одна з нерозв'язаних задач — чи є Kk єдиним двічі критичним k-хроматичним графомШаблон:Sfn.
Див. також
Примітки
Література
- Шаблон:Стаття
- Шаблон:Стаття. (Indag. Math. 13.)
- Шаблон:Стаття
- Шаблон:Стаття
- Шаблон:Стаття.
- Шаблон:Стаття
- Шаблон:Книга
- Шаблон:Стаття
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Стаття
- Шаблон:Книга
- ↑ Слід зазначити, що не завжди під критичним графом розуміють критичний k-хроматичний граф. У статті Візінга під критичним графом розмірності k розуміють граф, у якого розмірність будь-якої власної частини менша від k. Під розмірністю графа при цьому розуміють мінімальну розмірність метричного простору, в який можна вкласти граф так, що всі суміжні вершини опиняться на відстані 1. Шаблон:Harvard citation