Графы без X - это графы, которые не содержат графов из X в качестве индуцированного подграфа. Отверстие представляет собой цикл, по крайней мере 4 -х вершин. Нечетное отверстие представляет собой отверстие с нечетным числом вершин. Antihole является дополнением дырки.
Графики (нечетные дыры, нечетные дыры) являются в точности идеальными графами; это сильная теорема о совершенном графе . Можно найти самый большой независимый набор (и самую большую клику) в идеальном графе за полиномиальное время, но единственный известный способ сделать это требует создания полуопределенной программы для вычисления тэта-числа Ловаша .
Графы без дыр, без отверстий называются слабо хордовыми и представляют собой довольно легкий класс для многих задач (включая НЕЗАВИСИМЫЙ НАБОР и КЛИК ).
Кто-нибудь знает, были ли изучены или написаны (нечетные, анти-дырочные) графы?
Эти графы вполне естественно возникают в задачах удовлетворения ограничений, когда граф связанных переменных образует дерево. Такие проблемы довольно просты, поэтому было бы неплохо, если бы существовал способ найти самую большую независимую клику множеств для графов в этом семействе, не вычисляя тэту Ловаша.
Эквивалентно, каждый хочет найти самый большой независимый набор для (дырочных, нечетных-анти-дырочных) графов. Сянь-Чи Чанг ниже указывает, почему это более интересный класс для НЕЗАВИСИМОГО НАБОРА, чем (нечетные, анти-дырочные) графы.
источник