Граф минор

Подграф со сжатыми краями

В теории графов неориентированный граф H называется минором графа G , если H можно образовать из G путем удаления ребер, вершин и стягивания ребер .

Теория миноров графа началась с теоремы Вагнера о том, что граф планарен тогда и только тогда, когда его миноры не включают ни полный граф K ₅ , ни полный двудольный граф K _3,3 . ^[1] Теорема Робертсона-Сеймура подразумевает, что аналогичная запрещенная второстепенная характеристика существует для каждого свойства графов, которое сохраняется за счет удаления и сжатия ребер. ^[2] Для каждого фиксированного графа H можно проверить, является ли H минором входного графа G за полиномиальное время ; ^[3] вместе с запрещенной второстепенной характеристикой это означает, что каждое свойство графа, сохраненное за счет удалений и сокращений, может быть распознано за полиномиальное время. ^[4]

Другие результаты и гипотезы, связанные с минорами графа, включают теорему о структуре графа , согласно которой графы, не имеющие H в качестве минора, могут быть сформированы путем склеивания более простых частей, и гипотезу Хадвигера, связывающую невозможность раскрасить граф с существованием минора графа. большой полный граф как его минор. Важные варианты миноров графа включают топологические миноры и миноры погружения.

Определения

Сжатие ребра — это операция, которая удаляет ребро из графа и одновременно объединяет две вершины, которые оно использовало для соединения. Неориентированный граф H является минором другого неориентированного графа G , если граф, изоморфный H , может быть получен из G путем стягивания некоторых ребер, удаления некоторых ребер и удаления некоторых изолированных вершин. Порядок, в котором последовательность таких сокращений и удалений выполняется на G, не влияет на результирующий граф H.

Миноры графа часто изучаются в более общем контексте миноров матроидов . В этом контексте принято предполагать, что все графы связны, с допустимыми циклами и кратными ребрами (то есть они являются мультиграфами , а не простыми графами); сжатие петли и удаление среза являются запрещенными операциями. Преимущество этой точки зрения состоит в том, что удаление ребер оставляет ранг графа неизменным, а сжатие ребер всегда снижает ранг на единицу.

В других контекстах (например, при изучении псевдолесов ) имеет смысл разрешить удаление разреза и разрешить несвязные графы, но запретить мультиграфы. В этом варианте минорной теории графов граф всегда упрощается после любого сжатия ребра, чтобы исключить его петли и кратные ребра. ^[5]

Функция f называется «минорно-монотонной», если всякий раз, когда H является минором G , выполняется f ( H ) ≤ f ( G ) .

Пример

В следующем примере граф H является минорным графа G :

ЧАС.

Г.

Следующая диаграмма иллюстрирует это. Сначала создайте подграф G , удалив пунктирные ребра (и полученную изолированную вершину), а затем сжимая серое ребро (объединяя две вершины, которые оно соединяет):

Основные результаты и предположения

Непосредственно проверяется, что минорное отношение графа образует частичный порядок на классах изоморфизма конечных неориентированных графов: оно транзитивно (минор минора G является минором самого G ), а G и H могут быть только минорами. друг друга, если они изоморфны, поскольку любая нетривиальная второстепенная операция удаляет ребра или вершины. Глубокий результат Нила Робертсона и Пола Сеймура гласит, что этот частичный порядок на самом деле является хорошим квазиупорядочением : если задан бесконечный список ( G1 _, G2 _, …) конечных графов , то всегда существуют два индекса i < j такой, что G _i является минором G _j . Другой эквивалентный способ выразить это состоит в том, что любой набор графов может иметь только конечное число минимальных элементов при минорном порядке. ^[6] Этот результат доказал гипотезу, ранее известную как гипотеза Вагнера, в честь Клауса Вагнера ; Вагнер выдвинул эту гипотезу гораздо раньше, но опубликовал ее только в 1970 году. ^[7]

В ходе своего доказательства Сеймур и Робертсон также доказывают теорему о структуре графа , в которой они определяют для любого фиксированного графа H грубую структуру любого графа, который не имеет H в качестве минора. Формулировка теоремы сама по себе длинная и сложная, но вкратце она устанавливает, что такой граф должен иметь структуру клик -суммы меньших графов, которые немного модифицируются из графов, вложенных на поверхности ограниченного рода . Таким образом, их теория устанавливает фундаментальные связи между минорами графов и топологическими вложениями графов. ^[8]

Для любого графа H простые графы без H -миноров должны быть разреженными , что означает, что количество ребер меньше некоторого постоянного кратного числа вершин. ^[9] Точнее, если H имеет h вершин, то простой граф с n -вершинами без миноров может иметь не более ребер, а некоторые K _h -графы без миноров имеют по крайней мере такое же количество ребер. ^[10] Таким образом, если H имеет h вершин, то графы без миноров H имеют среднюю степень и, кроме того , вырожденность . Кроме того, графы без H -миноров имеют теорему о сепараторе, аналогичную теореме о плоском сепараторе для плоских графов: для любого фиксированного H и любого n -вершинного H -минорного графа G можно найти подмножество вершин удаление которого разбивает G на два (возможно, несвязных) подграфа с не более чем 2 n ⁄ 3 вершинами в каждом подграфе. ^[11] Более того, для любого фиксированного H графы без миноров H имеют древовидную ширину . ^[12] ${\displaystyle \scriptstyle O(nh{\sqrt {\log h}})}$ ${\displaystyle \scriptstyle O(h{\sqrt {\log h}})}$ ${\displaystyle \scriptstyle O(h{\sqrt {\log h}})}$ ${\displaystyle \scriptstyle O({\sqrt {n}})}$ ${\displaystyle \scriptstyle O({\sqrt {n}})}$

Гипотеза Хадвигера в теории графов предполагает, что если граф G не содержит минора, изоморфного полному графу на k вершинах, то G имеет правильную раскраску в k – 1 цвет. ^[13] Случай k = 5 является переформулировкой теоремы о четырех цветах . Гипотеза Хадвигера доказана для k ⩽ 6 ^[14] , но в общем случае она неизвестна. Боллобас, Катлин и Эрдеш (1980) называют это «одной из самых глубоких нерешенных проблем теории графов». Другой результат, связывающий теорему о четырех цветах с минорами графа, - это снарковская теорема, объявленная Робертсоном, Сандерсом, Сеймуром и Томасом, усиление теоремы о четырех цветах, выдвинутая У.Т. Туттом и утверждающая, что любой 3-регулярный граф без мостов , требующий четырех цвета в раскраске ребер должны иметь граф Петерсена в качестве минорного. ^[15]

Семейства минорно-замкнутых графов

Многие семейства графов обладают тем свойством, что каждый минор графа в F также находится в F ; такой класс называется минорно-закрытым . Например, в любом плоском графе или любом вложении графа в фиксированную топологическую поверхность ни удаление ребер, ни сжатие ребер не могут увеличить род вложения ; следовательно, плоские графы и графы, вложимые в любую фиксированную поверхность, образуют минорно-замкнутые семейства.

Если F — минорно-замкнутое семейство, то (в силу свойства хорошей квазиупорядоченности миноров) среди графов, не принадлежащих F , существует конечное множество X минорно-минимальных графов. Эти графы являются запрещенными минорами для F : граф принадлежит F тогда и только тогда, когда он не содержит в качестве минора ни одного графа из X. То есть каждое минорно-замкнутое семейство F можно охарактеризовать как семейство X -безминорных графов для некоторого конечного множества X запрещенных миноров. ^[2] Самым известным примером характеризации этого типа является теорема Вагнера , характеризующая плоские графы как графы, не имеющие ни K ₅ , ни K _3,3 в качестве миноров. ^[1]

В некоторых случаях свойства графов в минорно-замкнутом семействе могут быть тесно связаны со свойствами их исключенных миноров. Например, семейство замкнутых миноров графов F имеет ограниченную ширину пути тогда и только тогда, когда его запрещенные миноры включают в себя лес , ^[16] F имеет ограниченную глубину дерева тогда и только тогда, когда его запрещенные миноры включают в себя несвязное объединение графов путей , F имеет ограниченную глубину дерева. ширина дерева тогда и только тогда, когда его запрещенные миноры включают в себя плоский граф , ^[17] и F имеет ограниченную локальную ширину дерева (функциональную связь между диаметром и шириной дерева) тогда и только тогда, когда его запрещенные миноры включают вершинный граф (граф, который можно сделать плоским). удалением одной вершины). ^[18] Если H можно нарисовать на плоскости только с одним пересечением (то есть, он имеет пересечение номер один), то графы без миноров H имеют упрощенную структурную теорему, в которой они формируются как клик-суммы плоских графы и графы ограниченной древовидной ширины. ^[19] Например, и K ₅ , и K _3,3 имеют номер пересечения один, и, как показал Вагнер, графы, свободные от K ₅ , представляют собой в точности 3-кликовые суммы планарных графов и восьмивершинного графа Вагнера , в то время как K _3,3 -свободные графы представляют собой в точности 2-кликовые суммы планарных графов и  K ₅ . ^[20]

Вариации

Топологические миноры

Граф H называется топологическим минором графа G , если подразделение H изоморфно подграфу G . _ _ ^[21] Каждый топологический минор также является минором. Обратное, однако, неверно в общем случае (например, полный граф K ₅ в графе Петерсена является минорным, но не топологическим), но справедливо для графа с максимальной степенью не выше трех. ^[22]

Топологическое минорное отношение не является хорошим квазиупорядочением на множестве конечных графов ^[23], и, следовательно, результат Робертсона и Сеймура не применим к топологическим минорам. Однако легко построить конечные запрещенные топологические второстепенные характеристики из конечных запрещенных второстепенных характеризаций, заменив каждое множество ветвей с k исходящими ребрами каждым деревом на k листьях, которое имеет степень опускания не менее двух.

Индуцированные несовершеннолетние

Граф H называется индуцированным минором графа G , если его можно получить из индуцированного подграфа G стягиванием ребер. В противном случае G называется H -индуцированной минорной свободной группой. ^[24]

Погружение незначительное

Операция над графом, называемая подъемом, занимает центральное место в концепции, называемой погружением . Подъем представляет собой операцию на соседних ребрах. Учитывая три вершины v , u и w , где (v,u) и (u,w) — ребра в графе, подъем vuw или эквивалента (v,u), (u,w) — это операция который удаляет два ребра (v,u) и (u,w) и добавляет ребро (v,w) . В случае, когда (v,w) уже присутствовал, v и w теперь будут соединены более чем одним ребром, и, следовательно, эта операция по своей сути является операцией с несколькими графами.

В случае, когда граф H можно получить из графа G с помощью последовательности операций подъема (на G ) и последующего нахождения изоморфного подграфа, мы говорим, что H является минором погружения G . Существует еще один способ определения миноров погружения, эквивалентный операции подъема. Мы говорим, что H является иммерсионным минором группы G , если существует инъективное отображение вершин из H в вершины из G , где образы соседних элементов из H соединены в G путями, не пересекающимися по ребрам.

Минорное отношение погружения представляет собой хороший квазиупорядочение на множестве конечных графов, и, следовательно, результат Робертсона и Сеймура применим к минорам погружения. Кроме того, это означает, что каждое замкнутое семейство миноров погружения характеризуется конечным семейством запрещенных миноров погружения.

При рисовании графов миноры погружения возникают как планаризации неплоских графов : из рисунка графа на плоскости с пересечениями можно сформировать минор погружения, заменяя каждую точку пересечения новой вершиной, причем в процессе также разделение каждого пересекаемого ребра на путь. Это позволяет распространить методы рисования планарных графов на неплоские графы. ^[25]

Мелкие несовершеннолетние

Неглубокий минор графа G — это минор, в котором ребра G , сжавшиеся в минор, образуют набор непересекающихся подграфов с малым диаметром . Мелкие миноры интерполируют между теориями миноров и подграфов графа, поскольку мелкие миноры с большой глубиной совпадают с обычным типом минора графа, тогда как мелкие миноры с нулевой глубиной являются в точности подграфами. ^[26] Они также позволяют распространить теорию миноров графов на классы графов, таких как 1-планарные графы , которые не замкнуты относительно миноров. ^[27]

Условия паритета

Альтернативное и эквивалентное определение минора графа состоит в том, что H является минором графа G всякий раз, когда вершины H могут быть представлены набором непересекающихся по вершинам поддеревьев G , так что если две вершины смежны в H , существует ребро с его концами в соответствующих двух деревьях в G . Нечетный минор ограничивает это определение, добавляя к этим поддеревьям условия четности. Если H представлено набором поддеревьев G, как указано выше, то H является нечетным минором G , если возможно назначить два цвета вершинам G таким образом, чтобы каждое ребро G внутри поддерева было правильно раскрашено. (его конечные точки имеют разные цвета), и каждое ребро G , представляющее смежность между двумя поддеревьями, является одноцветным (обе его конечные точки имеют один и тот же цвет). В отличие от обычных миноров графа, графы с запрещенными нечетными минорами не обязательно являются разреженными. ^[28] Гипотеза Хадвигера о том, что k -хроматические графы обязательно содержат k -вершинные полные графы в качестве миноров, также изучалась с точки зрения нечетных миноров. ^[29]

Другим расширением понятия миноров графа, основанным на четности, является концепция двудольного минора, которая создает двудольный граф , когда исходный граф является двудольным. Граф H является двудольным минором другого графа G , если H можно получить из G удалением вершин, удалением ребер и схлопыванием пар вершин, находящихся на расстоянии двух друг от друга вдоль периферийного цикла графа. Форма теоремы Вагнера применима к двудольным минорам: Двудольный граф G является планарным графом тогда и только тогда, когда он не имеет графа полезности K _3,3 в качестве двудольного минора. ^[30]

Алгоритмы

Проблема определения того, содержит ли граф G H в качестве минора, в общем случае является NP-полной; например, если H — граф циклов с тем же количеством вершин, что и G , то H — минор графа G тогда и только тогда, когда G содержит гамильтонов цикл . Однако, когда G является частью входных данных, но H фиксировано, ее можно решить за полиномиальное время. Более конкретно, время выполнения проверки того, является ли H минором G, в этом случае равно O ( n ³ ), где n — количество вершин в G , а большое обозначение O скрывает константу, которая зависит суперэкспоненциально от H ; ^[3] после исходного результата Graph Minors этот алгоритм был улучшен до времени O ( n ² ). ^[31] Таким образом, применяя алгоритм полиномиального времени для проверки того, содержит ли данный граф какой-либо из запрещенных миноров, теоретически возможно распознавать членов любого минорно-замкнутого семейства за полиномиальное время . Этот результат не используется на практике, поскольку скрытая константа настолько велика (для выражения требуется три слоя нотации Кнута со стрелкой вверх ), что исключает любое применение, что делает его галактическим алгоритмом . ^[32] Кроме того, чтобы конструктивно применить этот результат, необходимо знать, каковы запрещенные миноры семейства графов. ^[4] В некоторых случаях запрещенные несовершеннолетние известны или могут быть вычислены. ^[33]

В случае, когда H — фиксированный планарный граф , мы можем за линейное время проверить во входном графе G , является ли H минором G. ^[34] В случаях, когда H не фиксировано, известны более быстрые алгоритмы в случае, когда G планарна. ^[35]

Примечания

1. Ловас (2006), стр. 77; Вагнер (1937а).
2. Lovász (2006), теорема 4, с. 78; Робертсон и Сеймур (2004).
3. Робертсон и Сеймур (1995).
4. Fellows & Langston (1988).
5. Ловас (2006) непоследователен в отношении того, разрешать ли циклы и множественные смежности: он пишет на стр. 76, что «допускаются параллельные ребра и петли», а на с. В статье 77 он утверждает, что «граф является лесом тогда и только тогда, когда он не содержит треугольника _К3 в качестве минора», что верно только для простых графов.
6. Дистель (2005), Глава 12: Несовершеннолетние, деревья и WQO; Робертсон и Сеймур (2004).
7. Ловас (2006), с. 76.
8. Ловас (2006), стр. 80–82; Робертсон и Сеймур (2003).
9. Мэдер (1967).
10. Косточка (1982); Косточка (1984); Томасон (1984); Томасон (2001).
11. Алон, Сеймур и Томас (1990); Плоткин, Рао и Смит (1994); Рид и Вуд (2009).
12. Гроэ (2003)
13. Хадвигер (1943).
14. Робертсон, Сеймур и Томас (1993).
15. Томас (1999); Пегг (2002).
16. Робертсон и Сеймур (1983).
17. Ловас (2006), Теорема 9, с. 81; Робертсон и Сеймур (1986).
18. Эппштейн (2000); Демейн и Хаджиагайи (2004).
19. Робертсон и Сеймур (1993); Демейн, Хаджиагайи и Тиликос (2002).
20. Вагнер (1937a); Вагнер (1937б); Холл (1943).
21. Дистель 2005, с. 20
22. Дистель 2005, с. 22
23. Дин (1996).
24. Бласиок и др. (2015)
25. Буххайм и др. (2014).
26. Нешетржил и Оссона де Мендес (2012).
27. Нешетржил и Оссона де Мендес (2012), стр. 319–321.
28. Каварабаяси, Кен-ичи ; Рид, Брюс ; Воллан, Пол (2011), «Алгоритм минорного графа с условиями четности», 52-й ежегодный симпозиум IEEE по основам компьютерных наук , Институт инженеров по электротехнике и электронике, стр. 27–36, номер документа : 10.1109/focs.2011.52, S2CID  17385711.
29. Гилен, Джим ; Джерардс, Берт; Рид, Брюс ; Сеймур, Пол ; Ветта, Адриан (2009), «О нечетно-минорном варианте гипотезы Хадвигера», Журнал комбинаторной теории , серия B, 99 (1): 20–29, doi : 10.1016/j.jctb.2008.03.006 , MR  2467815.
30. Чудновский, Мария ; Калай, Гил ; Нево, Эран; Новик, Изабелла ; Сеймур, Пол (2016), «Двудольные миноры», Журнал комбинаторной теории , серия B, 116 : 219–228, arXiv : 1312.0210 , doi : 10.1016/j.jctb.2015.08.001, MR  3425242, S2CID  14571660.
31. Каварабаяши, Кобаяши и Рид (2012).
32. Джонсон, Дэвид С. (1987). «Колонка NP-полноты: постоянное руководство (выпуск 19)». Журнал алгоритмов . 8 (2): 285–303. CiteSeerX 10.1.1.114.3864 . дои : 10.1016/0196-6774(87)90043-5. 
33. Бодлендер, Ханс Л. (1993). «Туристический путеводитель по Триширине» (PDF) . Акта Кибернетика . 11 : 1–21.См. конец раздела 5.
34. Бодлендер, Ханс Л. (1993). «Туристический путеводитель по Триширине» (PDF) . Акта Кибернетика . 11 : 1–21.Первый абзац после теоремы 5.3
35. Адлер, Изольда; Дорн, Фредерик; Фомин Федор Владимирович; Сау, Игнаси; Тиликос, Димитриос М. (1 сентября 2012 г.). «Быстрое незначительное тестирование на планарных графах» (PDF) . Алгоритмика . 64 (1): 69–84. дои : 10.1007/s00453-011-9563-9. ISSN  0178-4617. S2CID  6204674.

Рекомендации

• Алон, Нога ; Сеймур, Пол ; Томас, Робин (1990), «Теорема о разделителе для неплоских графов», Журнал Американского математического общества , 3 (4): 801–808, doi : 10.2307/1990903 , JSTOR  1990903, MR  1065053.
• Бласёк, Ярослав; Каминский, Марцин; Раймон, Жан-Флоран; Транк, Теофиль (2015), Индуцированные несовершеннолетние и хороший квазиупорядочение , arXiv : 1510.07135 , Бибкод : 2015arXiv151007135B.
• Боллобас, Б. ; Кэтлин, Пенсильвания; Эрдеш, Пол (1980), «Гипотеза Хадвигера верна почти для каждого графа», European Journal of Combinatorics , 1 (3): 195–199, doi : 10.1016/s0195-6698(80)80001-1.
• Буххайм, Кристоф; Чимани, Маркус; Гутвенгер, Карстен; Юнгер, Майкл; Мутцель, Петра (2014), «Пересечения и планаризация», Тамассия, Роберто (редактор), Справочник по рисованию и визуализации графиков , Дискретная математика и ее приложения (Бока-Ратон), CRC Press, Бока-Ратон, Флорида.
• Демейн, Эрик Д .; Хаджиагайи, Мохаммад Таги (2004), «Диаметр и ширина дерева в семействах второстепенных замкнутых графов, пересмотренный», Algorithmica , 40 (3): 211–215, doi : 10.1007/s00453-004-1106-1, S2CID  390856.
• Демейн, Эрик Д .; Хаджиагайи, Мохаммад Таги; Тиликос, Димитриос М. (2002), «1,5-приближение для древовидной ширины графов, исключая граф с одним второстепенным пересечением», Proc. 5-й международный семинар по аппроксимационным алгоритмам для комбинаторной оптимизации (APPROX 2002) , Конспекты лекций по информатике, том. 2462, Springer-Verlag, стр. 67–80, номер документа : 10.1007/3-540-45753-4_8.
• Дистель, Рейнхард (2005), Теория графов (3-е изд.), Берлин, Нью-Йорк: Springer-Verlag, ISBN 978-3-540-26183-4.
• Дин, Гуоли (1996), «Исключая длинный двойной путь», Журнал комбинаторной теории , серия B, 66 (1): 11–23, doi : 10.1006/jctb.1996.0002 , MR  1368512.
• Эппштейн, Дэвид (2000), «Диаметр и ширина дерева в семействах младших замкнутых графов», Algorithmica , 27 (3): 275–291, arXiv : math.CO/9907126 , doi : 10.1007/s004530010020, MR  1759751, S2CID  3172160.
• Товарищи, Майкл Р .; Лэнгстон, Майкл А. (1988), «Неконструктивные инструменты для доказательства разрешимости за полиномиальное время», Journal of the ACM , 35 (3): 727–739, doi : 10.1145/44483.44491 , S2CID  16587284.
• Гроэ, Мартин (2003), «Локальная ширина дерева, исключенные миноры и алгоритмы аппроксимации», Combinatorica , 23 (4): 613–632, arXiv : math/0001128 , doi : 10.1007/s00493-003-0037-9, S2CID  11751235.
• Хадвигер, Хьюго (1943), «Über eine Klassifikation der Streckunkomplexe», Vierteljschr. Натурфорш. Гес. Цюрих , 88 : 133–143..
• Холл, Дик Вик (1943), «Заметки о примитивных кривых перекоса», Бюллетень Американского математического общества , 49 (12): 935–936, doi : 10.1090/S0002-9904-1943-08065-2.
• Каварабаяси, Кеничи ; Кобаяши, Юсуке; Рид, Брюс (март 2012 г.), «Проблема непересекающихся путей в квадратичное время», Журнал комбинаторной теории, серия B , 102 (2): 424–435, doi : 10.1016/j.jctb.2011.07.004
• Косточка, Александр В. (1982), "Минимальное число Хадвигера для графов с заданной средней степенью вершин", Методы Дискрет. Анализ. (на русском языке), 38 : 37–58..
• Косточка, Александр В. (1984), «Нижняя граница числа графов Хадвигера по их средней степени», Combinatorica , 4 (4): 307–316, doi : 10.1007/BF02579141, S2CID  15736799.
• Ловас, Ласло (2006), «Теория граф-миноров», Бюллетень Американского математического общества , 43 (1): 75–86, doi : 10.1090/S0273-0979-05-01088-8.
• Мадер, Вольфганг (1967), «Homomorphieeigenschaften und mittlere Kantendichte von Graphen», Mathematische Annalen , 174 (4): 265–268, doi : 10.1007/BF01364272, S2CID  120261785.
• Нешетржил, Ярослав ; Оссона де Мендес, Патрис (2012), Разреженность: графы, структуры и алгоритмы , Алгоритмы и комбинаторика, том. 28, Springer, стр. 62–65, номер документа : 10.1007/978-3-642-27875-4, ISBN. 978-3-642-27874-7, МР  2920058.
• Пегг, Эд-младший (2002), «Рецензия на книгу: Колоссальная книга по математике» (PDF) , Уведомления Американского математического общества , 49 (9): 1084–1086, Бибкод : 2002ITED...49.1084A, doi : 10.1109/ТЭД.2002.1003756.
• Плоткин, Серж; Рао, Сатиш; Смит, Уоррен Д. (1994), «Неглубоко исключенные несовершеннолетние и улучшенное разложение графов», Proc. 5-й симпозиум ACM – SIAM. по дискретным алгоритмам (SODA 1994), стр. 462–470..
• Рид, Брюс ; Вуд, Дэвид Р. (2009), «Алгоритм с линейным временем для поиска разделителя в графе, исключая минор», ACM Transactions on Algorithms , 5 (4): Статья 39, doi : 10.1145/1597036.1597043, S2CID  760001.
• Робертсон, Нил ; Сеймур, Пол (1983), «Минорные графы. I. Исключение леса», Журнал комбинаторной теории, серия B , 35 (1): 39–61, doi : 10.1016/0095-8956(83)90079-5.
• Робертсон, Нил ; Сеймур, Пол Д. (1986), «Минорные графы. V. Исключение плоского графа», Journal of Combinatorial Theory, Series B , 41 (1): 92–114, doi : 10.1016/0095-8956(86)90030- 4
• Робертсон, Нил ; Сеймур, Пол Д. (1993), «Исключая граф с одним пересечением», Робертсон, Нил; Сеймур, Пол (ред.), Теория структуры графов: Proc. Совместная летняя исследовательская конференция AMS – IMS – SIAM по минорным графам , Современная математика, том. 147, Американское математическое общество , стр. 669–675..
• Робертсон, Нил ; Сеймур, Пол Д. (1995), «Незначительные графы. XIII. Проблема непересекающихся путей», Журнал комбинаторной теории, серия B , 63 (1): 65–110, doi : 10.1006/jctb.1995.1006.
• Робертсон, Нил ; Сеймур, Пол Д. (2003), «Незначительные графы. XVI. Исключение неплоского графа», Журнал комбинаторной теории, серия B , 89 (1): 43–76, doi : 10.1016/S0095-8956(03) 00042-Х.
• Робертсон, Нил ; Сеймур, Пол Д. (2004), «Незначительные графы. XX. Гипотеза Вагнера», Журнал комбинаторной теории, серия B , 92 (2): 325–357, doi : 10.1016/j.jctb.2004.08.001.
• Робертсон, Нил ; Сеймур, Пол ; Томас, Робин (1993), «Гипотеза Хадвигера для графов без K6» (PDF) , Combinatorica , 13 (3): 279–361, doi : 10.1007/BF01202354, S2CID  9608738.
• Томас, Робин (1999), «Недавние исключенные второстепенные теоремы для графов», Обзоры по комбинаторике, 1999 (Кентербери) (PDF) , London Math. Соц. Лекции. Сер., вып. 267, Кембридж: Кембриджский университет. Пресс, стр. 201–222, МР  1725004..
• Томасон, Эндрю (1984), «Экстремальная функция для сжатия графов», Mathematical Proceedings of the Cambridge Philosophical Society , 95 (2): 261–265, Бибкод : 1983MPCPS..95..261T, doi : 10.1017/S0305004100061521, S2CID  124801301.
• Томасон, Эндрю (2001), «Экстремальная функция для полных миноров», Журнал комбинаторной теории, серия B , 81 (2): 318–338, doi : 10.1006/jctb.2000.2013.
• Вагнер, Клаус (1937a), «Über eine Eigenschaft der ebenen Komplexe», Math. Анна. , 114 : 570–590, doi : 10.1007/BF01594196, S2CID  123534907.
• Вагнер, Клаус (1937b), «Über eine Erweiterung des Satzes von Kuratowski», Deutsche Mathematik , 2 : 280–285..

Внешние ссылки

• Вайсштейн, Эрик В. «Граф Минор». Математический мир .