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

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

-критичний граф — це критичний граф із хроматичним числом k. Граф G з хроматичним числом k є вершинно-k-критичним, якщо кожна з його вершин є критичним елементомСлід зазначити, що не завжди під критичним графом розуміють критичний k-хроматичний граф. У статті Візінга під критичним графом розмірності k розуміють граф, у якого розмірність будь-якої власної частини менша від k. Під розмірністю графа при цьому розуміють мінімальну розмірність метричного простору, в який можна вкласти граф так, що всі суміжні вершини опиняться на відстані 1. .

Властивості

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

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

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

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

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

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

Див. також Фактор-критичний граф

Примітки

Література

. (Indag. Math. 13.)

.