Топ питань
Часова шкала
Чат
Перспективи
Критичний граф
граф, у якому кожна вершина або ребро є критичним елементом З Вікіпедії, вільної енциклопедії
Remove ads
Критичний граф — граф, у якому видалення будь-якої вершини або ребра призводить до зменшення хроматичного числа графу.

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

- Хоча кожен реберно-критичний граф обов'язково є критичним, зворотне хибне. Наприклад, граф наведений праворуч, є 4-критичним, але не реберно-критичним[11].
Remove ads
Варіації та узагальнення
- Двічі критичний граф — це зв'язний граф, у якому видалення будь-якої пари суміжних вершин зменшує хроматичне число на 2. Одна з нерозв'язаних задач — чи є Kk єдиним двічі критичним k-хроматичним графом[12].
Див. також
- Фактор-критичний граф
Примітки
Література
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads