Критичний граф

Вгорі зліва — вершинно-критичний граф з хроматичним числом 6. Решта N-1 подграфов мають хроматичне число 5.

Критичний граф — граф, у якому видалення будь-якої вершини або ребра призводить до зменшення хроматичного числа графу.

Пов'язані визначення

• $k$-критичний граф — це критичний граф із хроматичним числом k.
• Граф G з хроматичним числом k є вершинно-k-критичним, якщо кожна з його вершин є критичним елементом.

Властивості

• Нехай G є k-критичним графом із n вершинами і m ребрами. Тоді:
  • G має тільки одну компоненту.
  • G — скінченний (теорема де Брёйна — Ердеша Шаблон:Sfn).
  • δ(G) ≥ k − 1, тобто будь-яка вершина суміжна щонайменше k − 1 іншим вершинам. Строгіше, G реберно (k − 1)-зв'язнийШаблон:Sfn.
  • Якщо граф G (k − 1)-регулярний (кожна вершина суміжна рівно k − 1 іншим), то граф G або є повним графом K_k, або непарним циклом (теорема БруксаШаблон:Sfn).
  • 2m ≥ (k − 1)n + k − 3Шаблон:Sfn.
  • 2m ≥ (k − 1)n + [(k − 3)/(k² − 3)]nШаблон:Sfn.
  • Або G можна розбити на два менших критичних графи з ребром між кожною парою вершин, де дві вершини беруться з різних частин, або граф G має щонайменше 2k − 1 вершинШаблон:Sfn. Строгіше, або G має розклад такого типу, або для кожної вершини v графу G існує k-розфарбування, в якому v є єдиною вершиною зі своїм кольором, а всі інші класи кольорів мають щонайменше дві вершиниШаблон:Sfn.

• Граф G є вершинно-критичним тоді і тільки тоді, коли для будь-якої вершини v існує оптимальне підхоже розфарбування, в якому вершина v одна представляє клас кольору.

• 1-критичних графів не існує.
• Єдиний 2-критичний граф — це K_2.
• Всі 3-критичні графи вичерпуються простими циклами непарної довжиниШаблон:Sfn.

• Як показав ХайошШаблон:Sfn, будь-який k-критичний граф можна сформувати з повного графу K_k комбінацією Шаблон:Нп з операцією ототожнення двох несуміжних вершин. Граф, утворений таким способом, завжди вимагає k кольорів у будь-якому правильному розфарбуванні.

4-критичний, але не реберно-критичний граф, оскільки $\chi (G-x)=4$

• Хоча кожен реберно-критичний граф обов'язково є критичним, зворотне хибне. Наприклад, граф наведений праворуч, є 4-критичним, але не реберно-критичнимШаблон:Sfn.

Варіації та узагальнення

• Двічі критичний граф — це зв'язний граф, у якому видалення будь-якої пари суміжних вершин зменшує хроматичне число на 2. Одна з нерозв'язаних задач — чи є K_k єдиним двічі критичним k-хроматичним графомШаблон:Sfn.

Див. також

• Фактор-критичний граф

Література

• Шаблон:Стаття
• Шаблон:Стаття. (Indag. Math. 13.)
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття.
• Шаблон:Стаття
• Шаблон:Книга
• Шаблон:Стаття
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Стаття
• Шаблон:Книга