Interested Article - Граф Мейнеля

В графе Мейнеля любой длинный нечётный цикл (такой как чёрный 5-цикл, показанный здесь) должен иметь по меньшей мере две хорды (зелёные)

Граф Мейнеля — это граф, в котором любой нечётный цикл длины пять и более имеет по меньшей мере две хорды, то есть два ребра, соединяющих несоседние вершины цикла . Хорды могут быть непересекающимися (как на рисунке), а могут и пересекаться.

Графы Мейнеля названы именем Генри Мейнеля (известного также по гипотезе Мейнеля ), который доказал в 1976 году, что они являются совершенными графами задолго до доказательства cильной гипотезы о совершенных графах , полностью описывающей совершенные графы. Тот же результат был независимо обнаружен Маркосяном и Карапетяном .

Совершенство

Графы Мейнеля являются подклассом совершенных графов. Любой порождённый подграф графа Мейнеля является другим графом Мейнеля и в любом графе Мейнеля размер наибольшей клики равен наименьшему числу цветов, необходимых для раскраски графа . Таким образом, графы Мейнеля удовлетворяют определению совершенных графов, что кликовое число равно хроматическому числу в любом порождённом подграфе .

Графы Мейнеля называются также очень сильно совершенными графами , поскольку (как предположил Мейнель и доказал Хланг) они могут быть описаны свойством, обобщающим определение свойства строго совершенных графов — в любом порождённом подграфе графа Мейнеля любая вершина принадлежит независимому множеству , которое пересекается с любой максимальной кликой .

Связанные классы графов

Графы Мейнеля содержат хордальные графы , графы чётности и их подклассы, интервальные графы , дистанционно-наследуемые графы , двудольные графы и рёберно совершенные графы .

Домик является совершенным графом, но не является графом Мейнеля

Хотя графы Мейнеля образуют очень общий подкласс графов, они не включают всех совершенных графов. Например, домик (пятиугольник с одной хордой) совершенен, но графом Мейнеля не является.

Алгоритмы и сложность

Графы Мейнеля можно распознать за полиномиальное время и некоторые задачи оптимизации на графах, включая раскраску графов , которые NP-трудны для произвольных графов, могут быть решены за полиномиальное время для графов Мейнеля .

Примечания

↑ от 28 июля 2019 на Wayback Machine , Information System on Graph Classes and their Inclusions, retrieved 2016-09-25.
↑ , с. 339–342.
↑ , с. 292–296.
, с. 302–312.
, с. 225–252.
, с. 231–240.
, с. 107–123.

Литература

Meyniel H. On the perfect graph conjecture // Discrete Mathematics . — 1976. — Т. 16 , вып. 4 . — С. 339–342 . — doi : .
С. Маркосян, И. Карапетян. О совершенных графах // ДАН Арм. ССР. — 1976. — Вып. 5 .
Hoàng C. T. On a conjecture of Meyniel // Journal of Combinatorial Theory . — 1987. — Т. 42 , вып. 3 . — С. 302–312 . — doi : .
Burlet M., Fonlupt J. Polynomial algorithm to recognize a Meyniel graph // Topics on perfect graphs. — North-Holland, Amsterdam, 1984. — Т. 88. — С. 225–252. — (North-Holland Math. Stud.). — doi : .
Hertz A. A fast algorithm for coloring Meyniel graphs // Journal of Combinatorial Theory . — 1990. — Т. 50 , вып. 2 . — С. 231–240 . — doi : .
Roussel F., Rusu I. An O ( n ² ) algorithm to color Meyniel graphs // Discrete Mathematics . — 2001. — Т. 235 , вып. 1—3 . — С. 107–123 . — doi : .