Граф минор

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

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

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

Определения

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

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

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

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

Пример

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

ЧАС.

Г.

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

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

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

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

Для любого графа $H$ простые графы без миноров должны быть $разреженными$ , что означает, что число ребер меньше некоторого постоянного кратного числа вершин. ^[9] Более конкретно, если $H$ имеет $h$ вершин, то простой $n$ -вершинный простой граф без $миноров$ может иметь не более ребер, и некоторые $K$ $h$ -вершинные графы без миноров имеют по крайней мере столько ребер. ^[10] Таким образом, если $H$ имеет $h$ вершин, то графы без $миноров$ имеют среднюю степень и, кроме того, вырожденность . Кроме того, графы без $миноров$ имеют теорему о разделителе, похожую на теорему о плоском разделителе для планарных графов: для любого фиксированного $H$ и любого $n-$ вершинного $графа$ без миноров $G$ можно найти подмножество вершин, удаление которых разбивает $G$ на два (возможно, несвязных) подграфа с не более чем $2$ $n$ $⁄$ $3$ вершинами на подграф. ^[11] Еще сильнее, для любого фиксированного $H$ графы , свободные от $H$ -миноров, имеют древовидную ширину . ^[12] $\scriptstyle O(nh{\sqrt {\log h}})$ $\scriptstyle O(h{\sqrt {\log h}})$ $\scriptstyle O(h{\sqrt {\log h}})$ $\scriptstyle O({\sqrt {n}})$ $.mw-parser-output .frac{white-space:nowrap}.mw-parser-output .frac .num,.mw-parser-output .frac .den{font-size:80%;line-height:0;vertical-align:super}.mw-parser-output .frac .den{vertical-align:sub}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}$ $\scriptstyle O({\sqrt {n}})$

Гипотеза Хадвигера в теории графов предполагает, что если граф $G$ не содержит минора, изоморфного полному графу на $k$ вершинах, то $G$ имеет правильную раскраску с $k - 1$ цветами. ^[13] Случай $k = 5$ является переформулировкой теоремы о четырех красках . Гипотеза Хадвигера была доказана для $k \leq 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 _{5 ,} так и K _3,3 имеют число пересечений один, и, как показал Вагнер, графы без K ₅ являются в точности суммами по 3 кликам планарных графов и графа Вагнера с восемью вершинами , в то время как графы без K _3,3 являются в точности суммами по 2 кликам планарных графов и K ₅ . ^[20]

Вариации

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

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

Примечания

^ Аб Ловас (2006), стр. 77; Вагнер (1937а).
^ ab Lovász (2006), теорема 4, с. 78; Робертсон и Сеймур (2004).
^ Робертсон и Сеймур (1995).
^ ab Fellows & Langston (1988).
^ Ловас (2006) непоследователен в вопросе о том, следует ли допускать петли и множественные смежности: на стр. 76 он пишет, что «параллельные ребра и петли допускаются», но на стр. 77 он утверждает, что «граф является лесом тогда и только тогда, когда он не содержит треугольник $K3$ $в$ качестве минора», что верно только для простых графов.
^ Дистель (2005), Глава 12: Миноры, деревья и WQO; Робертсон и Сеймур (2004).
^ Ловас (2006), стр. 76.
^ Ловас (2006), стр. 80–82; Робертсон и Сеймур (2003).
^ Мейдер (1967).
^ Косточка (1982); Косточка (1984); Томасон (1984); Томасон (2001).
^ Алон, Сеймур и Томас (1990); Плоткин, Рао и Смит (1994); Рид и Вуд (2009).
^ Гроэ (2003)
^ Хадвигер (1943).
^ Робертсон, Сеймур и Томас (1993).
^ Томас (1999); Пегг (2002).
^ Робертсон и Сеймур (1983).
^ Ловас (2006), Теорема 9, с. 81; Робертсон и Сеймур (1986).
^ Эппштейн (2000); Демейн и Хаджиагайи (2004).
^ Робертсон и Сеймур (1993); Демейн, Хаджиагайи и Тиликос (2002).
^ Вагнер (1937a); Вагнер (1937b); Холл (1943).
^ Дистель 2005, стр. 20
^ Дистель 2005, стр. 22
^ Дин (1996).
^ Бласиок и др. (2015)
^ Буххайм и др. (2014).
^ Нешетржил и Оссона де Мендес (2012).
^ Нешетржил и Оссона де Мендес (2012), стр. 319–321.
^ Каварабаяси, Кен-ичи ; Рид, Брюс ; Уоллан, Пол (2011), «Алгоритм младшего графа с условиями четности», 52-й ежегодный симпозиум IEEE по основам компьютерных наук , Институт инженеров по электротехнике и электронике, стр. 27–36, doi :10.1109/focs.2011.52, S2CID 17385711.
^ Geelen, Jim ; Gerards, Bert; Reed, Bruce ; Seymour, Paul ; Vetta, Adrian (2009), «О нечетно-минорном варианте гипотезы Хадвигера», Journal of Combinatori Theory , Series B, 99 (1): 20–29, doi : 10.1016/j.jctb.2008.03.006 , MR 2467815.
^ Чудновский, Мария ; Калай, Гил ; Нево, Эран; Новик, Изабелла ; Сеймур, Пол (2016), «Двудольные миноры», Журнал комбинаторной теории , серия B, 116 : 219–228, arXiv : 1312.0210 , doi : 10.1016/j.jctb.2015.08.001, MR 3425242, S2CID 14571660.
^ Каварабаяши, Кобаяши и Рид (2012).
^ Джонсон, Дэвид С. (1987). «Столбец NP-полноты: постоянное руководство (издание 19)». Журнал алгоритмов . 8 (2): 285–303. CiteSeerX 10.1.1.114.3864 . doi :10.1016/0196-6774(87)90043-5.
^ Бодлендер, Ханс Л. (1993). «Туристический путеводитель по Treewidth» (PDF) . Acta Cybernetica . 11 : 1–21.См. конец раздела 5.
^ Бодлендер, Ханс Л. (1993). «Туристический путеводитель по Treewidth» (PDF) . Acta Cybernetica . 11 : 1–21.Первый абзац после теоремы 5.3
^ Адлер, Изольда; Дорн, Фредерик; Фомин Федор Владимирович; Сау, Игнаси; Тиликос, Димитриос М. (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), «Гипотеза Хадвигера верна почти для каждого графа», Европейский журнал комбинаторики , 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.
Demaine, Erik D .; Hajiaghayi, MohammadTaghi; Thilikos, Dimitrios M. (2002), "1,5-аппроксимация для ширины дерева графов, исключая граф с одним пересечением в качестве минора", Proc. 5th International Workshop on Approximation Algorithms for Combinatory Optimization (APPROX 2002) , Lecture Notes in Computer Science, т. 2462, Springer-Verlag, стр. 67–80, doi :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.
Fellows, Michael R .; Langston, Michael A. (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 Streckkomplexe», 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, doi :10.1007/978-3-642-27875-4, ISBN 978-3-642-27874-7, МР 2920058.
Пегг, Эд младший (2002), «Обзор книги: Колоссальная книга математики» (PDF) , Notices of the American Mathematical Society , 49 (9): 1084–1086, Bibcode : 2002ITED...49.1084A, doi : 10.1109/TED.2002.1003756.
Плоткин, Серж; Рао, Сатиш; Смит, Уоррен Д. (1994), «Неглубокие исключенные миноры и улучшенные разложения графов», Труды 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. Исключение планарного графа», Журнал комбинаторной теории, Серия B , 41 (1): 92–114, doi : 10.1016/0095-8956(86)90030-4
Робертсон, Нил ; Сеймур, Пол Д. (1993), «Исключение графа с одним пересечением», в Робертсон, Нил; Сеймур, Пол (ред.), Теория структуры графа: Труды AMS–IMS–SIAM Совместной летней исследовательской конференции по второстепенным графам , Contemporary Mathematics, т. 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-X.
Робертсон, Нил ; Сеймур, Пол Д. (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. Soc. Lecture Note Ser., т. 267, Кембридж: Cambridge Univ. Press, стр. 201–222, MR 1725004.
Томасон, Эндрю (1984), «Экстремальная функция для стягиваний графов», Математические труды Кембриджского философского общества , 95 (2): 261–265, Bibcode : 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..

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

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