Граф без четных дырок

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

Аддарио-Берри и др. (2008) продемонстрировали, что каждый граф без четных дырок содержит бисимплициальную вершину (вершину, окрестность которой является объединением двух клик ), что разрешило гипотезу Рида. показали ошибочность доказательства Позднее Чудновский и Сеймур (2023) , которые дали правильное доказательство.

Признание

Конфорти и др. (2002b) предложили первый алгоритм распознавания полиномиального времени для графов без четных дырок, который работает в ${\mathcal {O}}(n^{40})$ время. ^[2]да Силва и Вушкович (2008) позже улучшили это до ${\mathcal {O}}(n^{19})$ . Чанг и Лу (2012) и Чанг и Лу (2015) улучшили это до ${\mathcal {O}}(n^{11})$ время.Самый известный в настоящее время алгоритм предложен Лаем, Лу и Торупом (2020), который работает в ${\mathcal {O}}(n^{9})$ время.

Хотя графы без четных дырок можно распознать за полиномиальное время, NP -полным является определение того, содержит ли граф четная дырка, включающая определенную вершину. ^[3]

Неизвестно, можно ли решить раскраску графа и задачу о максимальном независимом множестве за полиномиальное время на графах без четных дырок или они NP-полны.Однако максимальная клика может быть найдена в графах без четных дырок за полиномиальное время. ^[4]

Примечания

^ «Графики без четных циклов» , www.graphclasses.org , получено 12 марта 2023 г.
^ Конфорти и др. (2002b) представляют свой алгоритм и утверждают, что он работает за полиномиальное время, не давая явного анализа. Чудновский, Каварабаяши и Сеймур (2004) подсчитали, что он длится «около ${\mathcal {O}}(n^{40})$ ."
^ Бьенсток (1991)
^ Вушкович (2010) .

Ссылки

Аддарио-Берри, Луиджи; Чудновская Мария ; Хаве, Фредерик; Рид, Брюс ; Сеймур, Пол (2008), «Бисимплициальные вершины в графах без четных дырок», Журнал комбинаторной теории , серия B, 98 (6): 1119–1164, doi : 10.1016/j.jctb.2007.12.006
Бинсток, Дэн (1991), «О сложности проверки нечетных дыр и индуцированных нечетных путей», Discrete Mathematics , 90 (1): 85–92, doi : 10.1016/0012-365X(91)90098-M
Чудновская Мария ; Каварабаяси, Кеничи ; Сеймур, Пол (2004), «Обнаружение четных дыр», Журнал теории графов , 48 (2): 85–111, doi : 10.1002/jgt.20040 , S2CID 2945499
Конфорти, Микеле; Корнюжоль, Жерар ; Капур, Аджай; Вушкович, Кристина (январь 2002a), «Графы без четных дырок, часть I: Теорема о разложении» (PDF) , Journal of Graph Theory , 39 (1): 6–49, doi : 10.1002/jgt.10006 , S2CID 12947855
Конфорти, Микеле; Корнюжоль, Жерар ; Капур, Аджай; Вушкович, Кристина (август 2002 г.), «Графы без четных дырок, часть II: Алгоритм распознавания» (PDF) , Journal of Graph Theory , 40 (4): 238–266, doi : 10.1002/jgt.10045 , S2CID 15044085
да Силва, Мурило В.Г.; Вушкович, Кристина (2008), Разложение графов без четных дырок со звездчатыми разрезами и двумя соединениями
Чанг, Сянь-Чжи; Лу, Сюэ-И (январь 2012 г.), «Быстрый алгоритм распознавания графов без четных дырок», SODA '12: Материалы двадцать третьего ежегодного симпозиума ACM-SIAM по дискретным алгоритмам : 1286–1297, arXiv : 1311.0358 , doi : 10.1137/1.9781611973099.101 , ISBN 978-1-61197-210-8
Чанг, Сянь-Чжи; Лу, Сюэ-И (июль 2015 г.), «Быстрый алгоритм распознавания графов без четных дырок», Журнал комбинаторной теории, серия B , 113 : 141–161, arXiv : 1311.0358 , doi : 10.1016/j.jctb. 2015.02.001 , S2CID 1744497
Вушкович, Кристина (2010), «Графы без четных дырок: обзор» (PDF) , Applicable Analysis and Discrete Mathematics , 4 (2): 219–240, doi : 10.2298/AADM100812027V , JSTOR 43666110 , MR 2724633
Лай, Кай-Юань; Лу, Сюэ-И; Торуп, Миккель (2020), «Три в дереве в почти линейном времени», Макарычев, Константин; Макарычев Юрий; Тулсиани, Мадхур; Камат, Гаутама; Чужой, Джулия (ред.), Труды 52-го ежегодного симпозиума ACM SIGACT по теории вычислений, STOC 2020, Чикаго, Иллинойс, США, 22–26 июня 2020 г. , Ассоциация вычислительной техники, стр. 1279–1292, arXiv : 1909.07446 , дои : 10.1145/3357713.3384235
Чудновский, Мария; Сеймур, Пол (2023), «Графы без четных дырок все еще имеют бисимплициальные вершины» , Журнал комбинаторной теории, серия B , arXiv : 1909.10967 , doi : 10.1016/j.jctb.2023.02.009

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

«Графы без четных дырок» , Информационная система по классам графов и их включениям

[1] «Графики без четных циклов» , www.graphclasses.org , получено 12 марта 2023 г.

[2] Конфорти и др. (2002b) представляют свой алгоритм и утверждают, что он работает за полиномиальное время, не давая явного анализа. Чудновский, Каварабаяши и Сеймур (2004) подсчитали, что он длится «около ${\mathcal {O}}(n^{40})$ ."

[3] Бьенсток (1991)

[FOOTNOTEVušković2010-4] Вушкович (2010) .

[1]

[2]

[3]

[4]