Структура графов, которые исключают идеальное совпадение по четырем вершинам как индуцированный граф

Я заинтересован в понимании структуры класса графов , чтобы в четырех вершинах не было индуцированного вершинами подграфа, который был бы идеальным соответствием. Иными словами, для любых четырех вершин в если и - ребра, у графа должно быть как минимум еще одно ребро в четырех вершинах. Этот класс изучался ранее? Любые ссылки или идеи будут оценены. Мы понимаем этот класс, когда ограничены двудольными графами, но общий случай кажется более сложным. $G$ $a,b,c,d$ $G$ $ab$ $cd$

graph-theory Чандра Чекури
источник

Хочется добавить сюда важное свойство графов, а именно то, что количество максимальных независимых множеств в таких графах является полиномиальным по числу вершин. Фактически для любых фиксированных графов есть полиномиальное число максимальных независимых множеств. Смотрите следующую ссылку для получения дополнительной информации. «Сложность результатов на графиках с несколькими кликами». Дискретная математика и теоретическая информатика 9.1 (2007): 127-135.

2 K_{2}

$2K_2$

t

$t$

t K_{2}

$tK_2$

Чандра Чекури

Структура графов, которые исключают идеальное совпадение по четырем вершинам как индуцированный граф

Ответы: