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

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

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

У теорії графів багато важливих сімейств графів можна описати скінченним числом графів, які не належать сімейству, виключивши із сімейства всі графи, які містять будь-який з цих заборонених графів як (породжений) підграф або мінор. Прототипом явища є теорема Понтрягіна — Куратовського, яка стверджує, що граф планарний (граф, який можна намалювати на площині без перетинів) тоді й лише тоді, коли він не містить будь-якого з двох заборонених підграфів: повного графа 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	скінченний список заборонених породжених підграфів з мінімальним степенем ребер принаймні 2k^2 − 3k + 1	породжений підграф	[18][19]
Основні теореми
Сімейство, визначене породженою успадкованою властивістю	(не обов'язково скінченна) перешкоджальна множина	породжений підграф
Сімейство, визначене мінорною успадкованою властивістю	скінченна перешкоджальна множина	мінор графа	теорема Робертсона — Сеймура

Див. також

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

Примітки

1. Diestel Reinhard. Graph Theory. — Springer-Verlag, 2000. — Т. 173. — (Graduate Texts in Mathematics) — ISBN 0-387-98976-5..
2. Christopher Auer, Christian Bachmaier, Franz J. Brandenburg, Andreas Gleißner, Kathrin Hanauer, Daniel Neuwirth, Josef Reislhuber. 21st International Symposium, GD 2013, Bordeaux, France, September 23-25, 2013, Revised Selected Papers / Stephen Wismath, Alexander Wolff,. — 2013. — Т. 8242. — С. 107–118. — (Lecture Notes in Computer Science) — DOI:10.1007/978-3-319-03841-4_10..
3. A. Gupta, R. Impagliazzo. Proc. 32nd IEEE Symposium on Foundations of Computer Science (FOCS '91). — IEEE Computer Society, 1991. — С. 802–811. — DOI:10.1109/SFCS.1991.185452..
4. Neil Robertson, P. D. Seymour, Robin Thomas. Linkless embeddings of graphs in 3-space // Bulletin of the American Mathematical Society. — 1993. — Т. 28, вип. 1 (25 грудня). — С. 84–89. — arXiv:math/9301216. — DOI:10.1090/S0273-0979-1993-00335-5..
5. Béla Bollobás^[en]. p. 9 Modern Graph Theory. — Springer, 1998. — ISBN 0-387-98488-7.
6. Toshinobu Kashiwabara. Graph Theory and Algorithms, 17th Symposium of Research Institute of Electric Communication, Tohoku University, Sendai, Japan, October 24-25, 1980, Proceedings / Nobuji Saito, Takao Nishizeki. — Springer-Verlag, 1981. — Т. 108. — С. 171–181. — (Lecture Notes in Computer Science) — DOI:10.1007/3-540-10704-5\_15..
7. Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas. The strong perfect graph theorem // Annals of Mathematics. — 2006. — Т. 164, вип. 1 (25 грудня). — С. 51–229. — arXiv:math/0212070v1. — DOI:10.4007/annals.2006.164.51..
8. L. W. Beineke. Beiträge zur Graphentheorie / H. Sachs, H.-J. Voss, H.-J. Walter. — Leipzig : Teubner, 1968. — С. 17–33..
9. Ehab El-Mallah, Charles Colbourn. The complexity of some edge deletion problems // IEEE Transactions on Circuits and Systems. — 1988. — Т. 35, вип. 3 (25 грудня). — С. 354–362. — DOI:10.1109/31.1748..
10. K. Takamizawa, Takao Nishizeki, Nobuji Saito. Combinatorial problems on series-parallel graphs // Discrete Applied Mathematics. — 1981. — Т. 3, вип. 1 (25 грудня). — С. 75–76. — DOI:10.1016/0166-218X(81)90031-7..
11. Benson L. Joeris, Min Chih Lin, Ross M. McConnell, Jeremy P. Spinrad, Jayme L. Szwarcfiter. Linear-Time Recognition of Helly Circular-Arc Models and Graphs // Algorithmica. — 2009. — Т. 59, вип. 2 (25 грудня). — С. 215–239. — DOI:10.1007/s00453-009-9304-5.
12. Stéphane Földes, Peter L. Peter Hammer. Proceedings of the Eighth Southeastern Conference on Combinatorics, Graph Theory and Computing (Louisiana State Univ., Baton Rouge, La., 1977). — Winnipeg : Utilitas Math, 1977a. — Т. XIX. — С. 311–315. — (Congressus Numerantium)
13. Hans L. Bodlaender. A partial k-arboretum of graphs with bounded treewidth // Theoretical Computer Science. — 1998. — Т. 209, вип. 1–2 (25 грудня). — С. 1–45. — DOI:10.1016/S0304-3975(97)00228-4..
14. Hans L. Bodlaender, Dimitrios M. Thilikos. Graphs with branchwidth at most three // Journal of Algorithms. — 1999. — Т. 32, вип. 2 (25 грудня). — С. 167–194. — DOI:10.1006/jagm.1999.1011..
15. D. Seinsche. On a property of the class of n-colorable graphs // Journal of Combinatorial Theory, Series B. — 1974. — Т. 16, вип. 2 (25 грудня). — С. 191–193. — DOI:10.1016/0095-8956(74)90063-X.
16. Martin Charles Golumbic. Trivially perfect graphs // Discrete Mathematics. — 1978. — Т. 24, вип. 1 (25 грудня). — С. 105–107. — DOI:10.1016/0012-365X(78)90178-4.
17. Yury Metelsky, Regina Tyshkevich. On line graphs of linear 3-uniform hypergraphs // Journal of Graph Theory. — 1997. — Т. 25, вип. 4 (25 грудня). — С. 243–251. — DOI:10.1002/(SICI)1097-0118(199708)25:4<243::AID-JGT1>3.0.CO;2-K.
18. M. S. Jacobson, Andre E. Kézdy, Jeno Lehel. Recognizing intersection graphs of linear uniform hypergraphs // Graphs and Combinatorics. — 1997. — Т. 13 (25 грудня). — С. 359–367. — DOI:10.1007/BF03353014.
19. Ranjan N. Naik, S. B. Rao, S. S. Shrikhande, N. M. Singhi. Intersection graphs of k-uniform hypergraphs // European J. Combinatorics. — 1982. — Т. 3 (25 грудня). — С. 159–172. — DOI:10.1016/s0195-6698(82)80029-2.