В теории графов , неориентированный граф Н называется минор графа G , если Н может быть образован из G путем удаления ребер и вершин и сокращающихся краями .
Теория миноров графов началась с теоремы Вагнера о том, что граф является плоским тогда и только тогда, когда его миноры не содержат ни полного графа K 5, ни полного двудольного графа K 3,3 . [1] Из теоремы Робертсона – Сеймура следует, что аналогичная запрещенная минорная характеризация существует для каждого свойства графов, которое сохраняется с помощью удалений и стягиваний ребер. [2] Для каждого фиксированного графа H можно проверить, является ли H минором входного графа G за полиномиальное время ;[3] вместе с запрещенной минорной характеристикой это означает, что каждое свойство графа, сохраняемое удалениями и сжатиями, может быть распознано за полиномиальное время. [4]
Другие результаты и гипотезы, касающиеся миноров графов, включают теорему о структуре графов , согласно которой графы, в которых H не является минором, могут быть сформированы путем склеивания вместе более простых частей, и гипотезу Хадвигера, связывающую невозможность раскрасить граф с существованием большой полный граф как второстепенный. Важные варианты миноров графа включают топологические миноры и миноры погружения.
Определения
Сжатие ребер - это операция, которая удаляет ребро из графа при одновременном слиянии двух вершин, которые он использовал для соединения. Неориентированный граф Н является незначительным другим неориентированным графом G , если граф изоморфного с Н может быть получен из G стягивания некоторых ребер, удаления некоторых ребер и удаления некоторых изолированных вершин. Порядок , в котором последовательность таких сокращений и делеций выполняется на G не влияет на полученный график H .
Миноры графов часто изучаются в более общем контексте миноров матроидов . В этом контексте принято считать, что все графы связаны, с разрешенными петлями и множественными ребрами (то есть они являются мультиграфами, а не простыми графами); сокращение цикла и удаление обрезки - запрещенные операции. Эта точка зрения имеет то преимущество, что при удалении ребер ранг графа остается неизменным, а при сжатии ребер ранг всегда уменьшается на единицу.
В других контекстах (например, при изучении псевдолесов ) имеет смысл разрешить удаление режущей кромки и разрешить несвязные графы, но запретить мультиграфы. В этом варианте теории второстепенных графов граф всегда упрощается после любого стягивания ребер, чтобы исключить его петли и множественные ребра. [5]
Функция f называется «минорно-монотонной», если, когда H является минором G , выполняется f (H) ≤ f (G).
Пример
В следующем примере граф H является второстепенным графа G :
ЧАС.
ГРАММ.
Следующая диаграмма иллюстрирует это. Сначала создайте подграф графа G , удалив пунктирные ребра (и полученную изолированную вершину), а затем сожмите серое ребро (объединяя две вершины, которые он соединяет):
Основные результаты и предположения
Несложно проверить, что минорное отношение графа формирует частичный порядок на классах изоморфизма конечных неориентированных графов: оно транзитивно (минор минора G является минором самого G ), а G и H могут быть только минорами друг друга, если они изоморфны, потому что любая нетривиальная малая операция удаляет ребра или вершины. Глубокий результат на Нил Робертсон и Пола Сеймур утверждает , что этот частичный порядок на самом деле является хорошо квази-упорядочения : если бесконечный список G 1 , G 2 , ... конечных графов дается, то всегда существуют два индекса я < j такой, что G i является минором группы G j . Другой эквивалентный способ заявить об этом состоит в том, что любой набор графов может иметь только конечное число минимальных элементов при меньшем порядке. [6] Этот результат доказал гипотезу, ранее известную как гипотеза Вагнера в честь Клауса Вагнера ; Вагнер предположил ее задолго до этого, но опубликовал ее только в 1970 году [7].
В ходе своего доказательства Сеймур и Робертсон также доказывают теорему о структуре графа, в которой они определяют для любого фиксированного графа H грубую структуру любого графа, в котором H не является второстепенным. Формулировка теоремы сама по себе длинна и сложна, но вкратце она устанавливает, что такой граф должен иметь структуру клик-суммы меньших графов, которые незначительно модифицируются из графов, вложенных в поверхности ограниченного рода . Таким образом, их теория устанавливает фундаментальные связи между минорами графов и топологическими вложениями графов. [8]
Для любого графа H простые графы без H- миноров должны быть разреженными , что означает, что количество ребер меньше некоторого постоянного кратного количества вершин. [9] Более конкретно, если H имеет h вершин, то простой граф без H - миноров с n- вершинами может иметь не болеерёбер, а некоторые K h -безминорные графы имеют по крайней мере это количество рёбер. [10] Таким образом, если H имеет h вершин, то графы без H- миноров имеют среднюю степеньи к тому же вырождение . Кроме того, у H -свободных графов есть теорема о разделителе, аналогичная теореме о плоском разделителе для плоских графов: для любого фиксированного H и любого n -вершинного H -безминорного графа G можно найти подмножествовершины, удаление которых разбивает G на два (возможно несвязных) подграфа с не более чем 2 n / 3 вершинами на подграф. [11] Еще сильнее, при любом фиксированном Н , Н -минор свободных график имеют древесную ширину . [12]
Гипотеза Хадвигер в теории графов предполагает , что если граф G не содержит небольшую изоморфно полный граф на K вершинах, то G имеет правильную раскраску с к - 1 цветам. [13] Случай k = 5 является переформулировкой теоремы о четырех цветах . Гипотеза Хадвигера была доказана для k ≤ 6 [14], но в общем случае неизвестна. Боллобас, Катлин и Эрдеш (1980) называют это «одной из самых глубоких нерешенных проблем теории графов». Другой результат, связывающий теорему о четырех цветах с минорами графов, - это теорема Снарка, объявленная Робертсоном, Сандерсом, Сеймуром и Томасом, усиление теоремы о четырех цветах , выдвинутой В. Т. Тутте и утверждающей, что любой 3-регулярный граф без мостов , требующий четырех цвета в раскраске ребер должны иметь граф Петерсена как второстепенный. [15]
Семейства минор-замкнутых графов
Многие семейства графов обладают тем свойством, что каждый минор графа из F также принадлежит F ; такой класс называется минорно-закрытым . Например, в любом плоском графе или любом вложении графа на фиксированную топологическую поверхность ни удаление ребер, ни сжатие ребер не может увеличить род вложения; поэтому плоские графы и графы, вложимые на любую фиксированную поверхность, образуют минно-замкнутые семейства.
Если F - минор-замкнутое семейство, то (из-за свойства квазиупорядоченности миноров) среди графов, не принадлежащих F, есть конечное множество X минорно-минимальных графов. Эти графики запрещено несовершеннолетним для F : график принадлежит F тогда и только тогда , когда он не содержит в качестве минора любого графа в X . То есть, каждый минорного замкнутого семейство F можно охарактеризовать как семейство X -минор свободных графы для некоторого конечного множества X запрещенных несовершеннолетних. [2] Наиболее известным примером характеризации этого типа является теорема Вагнера, характеризующая плоские графы как графы, не имеющие в качестве миноров K 5 или K 3,3 . [1]
В некоторых случаях свойства графов в минорно-замкнутом семействе могут быть тесно связаны со свойствами их исключенных миноров. Например, семейство минорных замкнутых графов F имеет ограниченную ширину пути тогда и только тогда, когда его запрещенные миноры включают лес , [16] F имеет ограниченную древовидную глубину тогда и только тогда, когда его запрещенные миноры включают несвязное объединение графов путей , F имеет ограниченную Treewidth тогда и только тогда, когда его запрещенные миноры включают в себя планарный граф , [17] и F имеет ограниченную локальную ширину дерева (функциональную связь между диаметром и шириной дерева) тогда и только тогда, когда его запрещенные миноры включают в себя вершинный граф (граф, который может быть сделан плоским удалением одной вершины). [18] Если H можно нарисовать на плоскости только одним перекрестком (т. Е. Он имеет перекресток номер один), то графы без H- миноров имеют упрощенную структурную теорему, в которой они образуются как клик-суммы плоских графы и графы ограниченной древовидной ширины. [19] Например, и K 5, и K 3,3 имеют пересечение номер один, и, как показал Вагнер, K 5 -свободные графы - это в точности 3-кликовые суммы плоских графов и восьмивершинного графа Вагнера , в то время как K 3,3 -свободные графы - это в точности 2-клик-суммы плоских графов и K 5 . [20]
Вариации
Топологические несовершеннолетние
Граф Н называется топологическим минор графа 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 теперь будут связаны более чем одним ребром, и, следовательно, эта операция по сути является операцией с несколькими графами.
В случае , когда график Н может быть получен из графа G с помощью последовательности подъемных операций (на G ) , а затем найти изоморфный подграф, мы говорим , что Н является погружение минора G . Есть еще один способ определения миноров погружения, который эквивалентен операции подъема. Мы говорим, что H - минор погружения группы G, если существует инъективное отображение из вершин H в вершины G, где образы соседних элементов H соединены в G рёберно непересекающимися путями.
Отношение минора погружения является хорошо квазиупорядоченным на множестве конечных графов, и, следовательно, результат Робертсона и Сеймура применим к минорам погружения. Это, кроме того, означает, что каждое замкнутое семейство миноров погружения характеризуется конечным семейством запрещенных миноров погружения.
В графе чертеже , погружные несовершеннолетние возникают как planarizations из неплоских графов : из чертежа графа на плоскости, с пересечениями, можно образовать погружение минора, заменив каждую точку пересечения с помощью новой вершины, и в этом процессе также разделяя каждое пересеченное ребро на путь. Это позволяет распространить методы рисования для планарных графов на неплоские графы. [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 3 ), где n - количество вершин в G, а большая нотация O скрывает константу, сверхэкспоненциально зависящую от H ; [3] с момента получения первоначального результата Graph Minors, этот алгоритм был улучшен до O ( n 2 ) раз. [31] Таким образом, применяя алгоритм полиномиального времени для проверки того, содержит ли данный граф какой-либо из запрещенных миноров, теоретически возможно распознать членов любого минорно-замкнутого семейства за полиномиальное время . Этот результат не используется на практике, поскольку скрытая константа настолько велика ( для выражения требуется три уровня нотации Кнута, направленной вверх ), что исключает любое приложение, что делает его галактическим алгоритмом . [32] Кроме того, чтобы применить этот результат конструктивно, необходимо знать, что такое запрещенные миноры семейства графов. [4] В некоторых случаях запрещенные несовершеннолетние известны или могут быть вычислены. [33]
В случае , когда Н является фиксированным плоским графом , то можно проверить в линейное время во входном графе G является ли Н является минором G . [34] В случаях, когда H не фиксировано, известны более быстрые алгоритмы в случае, когда G является плоским. [35]
Заметки
- ^ а б Ловас (2006) , стр. 77; Вагнер (1937а) .
- ^ a b Ловас (2006) , теорема 4, с. 78; Робертсон и Сеймур (2004) .
- ^ a b Робертсон и Сеймур (1995) .
- ^ a b Fellows & Langston (1988) .
- ^ Ловас (2006) не согласен с тем, разрешать ли петли и множественные смежности: он пишет на стр. 76, что «разрешены параллельные края и петли», но на стр. 77 он утверждает, что «граф является лесом тогда и только тогда, когда он не содержит треугольник K 3 как минор», что верно только для простых графов.
- ^ Diestel (2005) , глава 12: Несовершеннолетние, деревья, и WQO; Робертсон и Сеймур (2004) .
- ^ Lovász (2006) , стр. 76.
- ^ Lovász (2006) , стр 80-82. Робертсон и Сеймур (2003) .
- ^ Мадер (1967) .
- ↑ Косточка (1982) ; Косточка (1984) ; Томасон (1984) ; Томасон (2001) .
- ↑ Алон, Сеймур и Томас (1990) ; Плоткин, Рао и Смит (1994) ; Рид и Вуд (2009) .
- ^ Grohe (2003)
- ^ Хадвигер (1943) .
- ↑ Робертсон, Сеймур и Томас (1993) .
- ^ Томас (1999) ; Пегг (2002) .
- ↑ Робертсон и Сеймур (1983) .
- ^ Lovász (2006) , теорема 9, стр. 81; Робертсон и Сеймур (1986) .
- ^ Эпштайна (2000) ; Demaine и Hajiaghayi (2004) .
- ^ Робертсон и Сеймур (1993) ; Demaine, Hajiaghayi & Thilikos (2002) .
- ^ Вагнер (1937a) ; Вагнер (1937б) ; Холл (1943) .
- ^ Diestel 2005 , стр. 20
- ^ Diestel 2005 , стр. 22
- Перейти ↑ Ding (1996) .
- ^ Błasiok et al.
- ^ Buchheim et al. (2014) .
- ^ Nešetřil & Ossona де Мендес (2012) .
- ^ Nešetřil & Ossona де Мендес (2012) , стр. 319-321.
- ^ Kawarabayashi, Кэнъити ; Рид, Брюс ; Воллан, Пол (2011), «Малый алгоритм графа с условиями четности», 52-й ежегодный симпозиум IEEE по основам информатики , Институт инженеров по электротехнике и электронике, стр. 27–36, doi : 10.1109 / focs.2011.52 , S2CID 17385711.
- ^ Гилен, Джим ; Джерардс, Берт; Рид, Брюс ; Сеймур, Пол ; Vetta, Адриан (2009), "На нечетной малой вариант гипотезы Хадвигера" , Журнал комбинаторной теории , серии 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.
- ^ Kawarabayashi, Kobayashi & Reed (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.
- ^ Адлер, Изольда; Дорн, Фредерик; Фомин, Федор В .; Сау, Игнаси; Тиликос, Димитриос М. (01.09.2012). «Быстрое второстепенное тестирование в плоских графах» (PDF) . Алгоритмика . 64 (1): 69–84. DOI : 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 , Bibcode : 2015arXiv151007135B.
- Боллобаш, Б .; Catlin, PA; Erdős, Павел (1980), "гипотеза Хадвигера верно практически для любого графа" (PDF) , Европейский журнал Комбинаторика , 1 (3): 195-199, DOI : 10.1016 / s0195-6698 (80) 80001-1 , архивируются из оригинала (PDF) от 18.03.2009.
- Буххайм, Кристоф; Чимани, Маркус; Гутвенгер, Карстен; Юнгер, Михаэль; Mutzel, Petra (2014), «Пересечения и планаризация», в Tamassia, Roberto (ed.), Handbook of Graph Drawing and Visualization , Discrete Mathematics and its Applications (Boca Raton), CRC Press, Boca Raton, FL.
- Демейн, Эрик Д .; Hajiaghayi, MohammadTaghi (2004), "Диаметр и древесная ширина в минорных замкнутый граф семей, Revisited" , Algorithmica , 40 (3): 211-215, DOI : 10.1007 / s00453-004-1106-1 , S2CID 390856.
- Демейн, Эрик Д .; Хаджиагайи, Мохаммад Таги; Thilikos, Dimitrios M. (2002), "1.5-аппроксимация древовидной ширины графов, исключая граф с одним пересечением в качестве второстепенного", Proc. 5-й международный семинар по алгоритмам приближения для комбинаторной оптимизации (APPROX 2002) , Lecture Notes in Computer Science, 2462 , Springer-Verlag, pp. 67–80, doi : 10.1007 / 3-540-45753-4_8
- Дистель, Рейнхард (2005), Теория графов (3-е изд.), Берлин, Нью-Йорк: Springer-Verlag, ISBN 978-3-540-26183-4.
- Дин, Guoli (1996), "Исключая длинный путь двойной минор", Журнал комбинаторной теории , Series B, 66 (1): 11-23, DOI : 10,1006 / jctb.1996.0002 , МР 1368512.
- Эпштейн, Дэвид (2000), «Диаметр и ширина дерева в семействах второстепенных замкнутых графов», Algorithmica , 27 (3): 275–291, arXiv : math.CO/9907126 , doi : 10.1007 / s004530010020 , MR 1759751 , S2CID 3172160.
- Товарищи, Майкл Р .; Langston, Майкл А. (1988), "Неконструктивные инструменты для доказательства полиномиальной разрешимости", Журнал ACM , 35 (3): 727-739, DOI : 10,1145 / 44483,44491 , S2CID 16587284.
- Grohe, Martin (2003), «Локальная ширина дерева, исключенные миноры и алгоритмы аппроксимации», Combinatorica , 23 (4): 613–632, arXiv : math / 0001128 , doi : 10.1007 / s00493-003-0037-9 , S2CID 11751235.
- Hadwiger, Hugo (1943), "Über eine Klassifikation der Streckenkomplexe", Vierteljschr. Naturforsch. Ges. Цюрих , 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 унд Mittlere Kantendichte фон графена", 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, MR 2920058.
- Пегг, Эд, младший (2002), «Рецензия на книгу: Колоссальная книга математики» (PDF) , Уведомления Американского математического общества , 49 (9): 1084–1086, Bibcode : 2002ITED ... 49.1084A , doi : 10.1109 / TED.2002.1003756.
- Плоткин, Серж; Рао, Сатиш; Смит, Уоррен Д. (1994), "Мелкие исключенные миноры и улучшенные разложения графа", Proc. 5-й симпозиум ACM – SIAM. по дискретным алгоритмам (SODA 1994) , стр. 462–470..
- Рид, Брюс ; Вуд, Дэвид Р. (2009), «Линейное времени алгоритм поиска разделитель в графе за исключением несовершеннолетнего», ACM Сделки по алгоритмам , 5 (4): Статья 39, DOI : 10,1145 / 1597036,1597043 , S2CID 760001.
- Робертсон, Нил ; Seymour, Павел (1983), "Graph несовершеннолетних I. За исключением леса.", Журнал комбинаторной теории, серии B , 35 (1): 39-61, DOI : 10,1016 / 0095-8956 (83) 90079-5.
- Робертсон, Нил ; Сеймура, Пол Д. (1986), "Graph несовершеннолетнего В. За исключение плоского графа.", Журнал комбинаторной теории, Series B , 41 (1): 92-114, DOI : 10,1016 / 0095-8956 (86) 90030- 4
- Робертсон, Нил ; Сеймур, Пол Д. (1993), «Исключение графа с одним пересечением», Робертсон, Нил; Сеймур, Пол (ред.), Теория структуры графов: Proc. Совместная летняя исследовательская конференция AMS – IMS – SIAM по второстепенным графам , Современная математика, 147 , Американское математическое общество , стр. 669–675.
- Робертсон, Нил ; Seymour, Paul D. (1995), "Graph Несовершеннолетних XIII дизъюнктного путем проблема..", Журнал комбинаторной теории, серии B , 63 (1): 65-110, DOI : 10,1006 / jctb.1995.1006.
- Робертсон, Нил ; Seymour, Пол Д. (2003), "Graph Несовершеннолетние 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), "гипотеза Хадвигера для K 6 -свободных графов" (PDF) , Combinatorica , 13 (3): 279-361, DOI : 10.1007 / BF01202354 , S2CID 9608738.
- Томас, Робин (1999), «Недавние исключенные второстепенные теоремы для графов», Обзоры по комбинаторике, 1999 (Кентербери) (PDF) , London Math. Soc. Lecture Note Ser., 267 , Cambridge: Cambridge Univ. Press, стр. 201–222, MR 1725004.
- Томасон, Эндрю (1984), "Экстремальная функция для сжатия графов", Математические слушания Кембриджского философского общества , 95 (2): 261–265, Bibcode : 1983MPCPS..95..261T , doi : 10.1017 / S0305004100061521.
- Томасон, Эндрю (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), "Uber eine Erweiterung des Satzes von Kuratowski", Deutsche Mathematik , 2 : 280–285.
Внешние ссылки
- Вайсштейн, Эрик В. «Граф Минор» . MathWorld .