Характеризація забороненими графами

Характериза́ція заборо́неними гра́фами — це метод опису сімейства графів або гіперграфів вказанням підструктур, яким заборонено з'являтися всередині будь-якого графа сімейства.

Заборонені графи

У теорії графів багато важливих сімейств графів можна описати скінченним числом графів, які не належать сімейству, виключивши із сімейства всі графи, які містять будь-який з цих заборонених графів як (породжений) підграф або мінор. Прототипом явища є теорема Понтрягіна — Куратовського, яка стверджує, що граф планарний (граф, який можна намалювати на площині без перетинів) тоді й лише тоді, коли він не містить будь-якого з двох заборонених підграфів: повного графа K₅ і повного двочасткового графа K_3,3.

У різних сімействах природа забороненого змінюється. В загальному випадку структура G є членом сімейства ${\displaystyle {\mathcal {F}}}$ тоді й лише тоді, коли заборонена структура не міститься в G. Заборонена підструктура може бути однією з:

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

Множину структур, яким заборонено належати даному сімейству графів, можна також назвати перешкоджальною множиною сімейства.

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

Щоб сімейство мало характеризацію забороненими графами з певним типом підструктур, воно має бути замкнутим за підструктурами. Тобто будь-яка підструктура (даного типу) графа в сімействі повинна бути іншим графом у сімействі. Еквівалентно, якщо граф не входить у сімейство, всі більші графи, які містять його як підструктуру, мають бути виключені із сімейства. Якщо це так, завжди існує перешкоджальна множина (множина графів, які не належать сімейству, але всі менші їх підструктури належать сімейству). Проте, при деяких поданнях, що розуміти під підструктурою, ця перешкоджальна множина може виявитися нескінченною. Теорема Робертсона — Сеймура доводить, що в певних випадках мінорів графа, сімейство, замкнуте за мінорами, завжди має скінченну перешкоджальну множину.

Список характеризацій забороненими графами (для графів і гіперграфів)

Сімейство	Заборонені графи	Залежність	Зв'язок
Ліси	петлі, пари паралельних ребер і цикли будь-якої довжини	підграф	визначення
	петля (для мультиграфів) або трикутник K3 (для простих графів)	мінор графа	визначення
Графи без клешень	зірка K1,3	породжений підграф	визначення
Графи порівнянності		породжений підграф
Графи без трикутників	трикутник K3	породжений підграф	визначення
Планарні графи	K5 і K3,3	гомеоморфний підграф	теорема Понтрягіна — Куратовського
	K5 і K3,3	мінор графа	теорема Вагнера
Зовніпланарні графи	K4 і K2,3	мінор графа	Дістель[1] стор. 107
Зовнішні 1-планарні графи	п'ять заборонених мінорів	мінор графа	Авер, Бахмаєр та ін.[2]
Графи з фіксованим родом	скінченна перешкоджальна множина	мінор графа	Дістель стор. 275
Верхівковий граф	скінченна перешкоджальна множина	мінор графа	[3]
Графи, що допускають вкладення без зачеплень	петерсенове сімейство графів	мінор графа	[4]
Двочасткові графи	непарні цикли	підграф	[5]
Хордальні графи	цикли довжини 4 або більше	породжений підграф	[6]
Досконалі графи	непарні цикли довжини 5 і більше та їх доповнення	породжений підграф	[7]
Реберні графи для графів	дев'ять заборонених підграфів (перелічені тут)	породжений підграф	[8]
Об'єднання графів-кактусів	алмаз, утворений видаленням ребра з повного графа K4	мінор графа	[9]
Драбини	K2,3 і його двоїстий граф	гомеоморфний підграф	[10]
Циркулярні графи дуг Геллі		породжений підграф	[11]
Розщепні графи	${\displaystyle C_{4},C_{5},{\bar {C_{4}}}(=K_{2}+K_{2})}$	породжений підграф	[12]
Паралельно-послідовні графи (деревна ширина ≤ 2, ширина галуження ≤ 2)	K4	мінор графа	Дістель стор. 327
Деревна ширина ≤ 3	K5, октаедр, п'ятикутна призма, граф Вагнера	мінор графа	[13]
Ширина галуження ≤ 3	K5, октаедр, куб, граф Вагнера	мінор графа	[14]
Додатково звідні графи (кографи)	Граф P4	породжений підграф	[15]
Тривіально досконалі графи	Граф P4 і цикл C4	породжений підграф	[16]
Порогові графи	Граф P4, цикл C4 і доповнення C4	породжений підграф
Реберні графи 3-однорідних лінійних гіперграфів	скінченний список заборонених породжених підграфів з мінімальним степенем, не меншим від 19	породжений підграф	[17]
Реберні графи k-однорідні лінійні гіперграфи, k > 3	скінченний список заборонених породжених підграфів з мінімальним степенем ребер принаймні 2k2 − 3k + 1	породжений підграф	[18][19]
Основні теореми
Сімейство, визначене породженою успадкованою властивістю	(не обов'язково скінченна) перешкоджальна множина	породжений підграф
Сімейство, визначене мінорною успадкованою властивістю	скінченна перешкоджальна множина	мінор графа	теорема Робертсона — Сеймура

Див. також

• Гіпотеза Ердеша — Гайналя
• Задача про заборонені підграфи^[en]
• Мінор матроїда^[en]
• Задача Заранкевича