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

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

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

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

У різних сімействах природа забороненого змінюється. В загальному випадку структура G є членом сімейства тоді й лише тоді, коли заборонена структура не міститься в 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]
Розщепні графи породжений підграф [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]
Основні теореми
Сімейство, визначене породженою успадкованою властивістю (не обов'язково скінченна) перешкоджальна множина породжений підграф
Сімейство, визначене мінорною успадкованою властивістю скінченна перешкоджальна множина мінор графу теорема Робертсона — Сеймура

Див. також
  • Гіпотеза Ердеша — Гайналя
  • Задача про заборонені підграфи
  • Мінор матроїда
  • Задача Заранкієвича

Примітки
  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 (21 січня). — С. 84–89. — arXiv:math/9301216. — DOI:10.1090/S0273-0979-1993-00335-5..
  5. Béla Bollobás. 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 (21 січня). — С. 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 (21 січня). — С. 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 (21 січня). — С. 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 (21 січня). — С. 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 (21 січня). — С. 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 (21 січня). — С. 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 (21 січня). — С. 191–193. — DOI:10.1016/0095-8956(74)90063-X.
  16. Martin Charles Golumbic. Trivially perfect graphs // Discrete Mathematics. — 1978. — Т. 24, вип. 1 (21 січня). — С. 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 (21 січня). — С. 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 (21 січня). — С. 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 (21 січня). — С. 159–172. — DOI:10.1016/s0195-6698(82)80029-2.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.