Максимальные / максимальные независимые множества

Известно ли что-нибудь о классе графов с тем свойством, что все максимальные независимые множества имеют одинаковую мощность и, следовательно, являются максимальными IS?

Например, возьмем набор точек на плоскости и рассмотрим график пересечений между всеми отрезками между парами точек в наборе. (отрезки-> вершины, пересечения-> ребра). Этот граф будет иметь указанное выше свойство, так как все максимальные IS соответствуют триангуляциям исходного набора точек. Известны ли другие категории графиков, обладающих этим свойством? Может ли это свойство быть легко проверено?

Такие графы называются хорошо покрытыми графами. Вот недавняя статья на эту тему, в которой перечислено несколько полезных ссылок. Как упомянул Суреш, проблема распознавания является со-NP-полной.

Обратите внимание, что независимые множества графа образуют абстрактный симплициальный комплекс. Симплициальные комплексы, возникающие таким образом, называются «комплексами независимости» или «флаговыми комплексами». Симплициальный комплекс называется чистым, если каждый максимальный симплекс имеет одинаковую мощность. Таким образом, вы можете найти некоторые релевантные документы, выполнив поиск «комплекс чистой независимости» или «комплекс чистого флага».

Важным является свойство MAXIMAL = MAXIMUM для независимых множеств в графах и более общих комбинаторных структурах. Будет интересно понять графики, где это свойство выполняется для всех индуцированных подграфов. Один общий абстрактный случай, когда у нас MAXIMUM = MAXIMAL, - это когда есть основная структура матроида, но есть много других случаев, таких как случай максимальных плоских графов, упомянутых в вопросе. Вот соответствующий пример: рассмотрим n точек на плоскости в выпуклом положении, и пусть k будет целым числом. Рассмотрим графы, вершинами которых являются отрезки между этими точками, где две вершины смежны, если отрезки не пересекаются. Дресс доказал, что для этого графика MAXIMIM = MAXIMAL для независимых множеств.