Граф Мейнеля

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

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

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

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

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

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

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

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

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

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

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

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

Примечания

1. Meyniel graphs Архивная копия от 28 июля 2019 на Wayback Machine, Information System on Graph Classes and their Inclusions, retrieved 2016-09-25.
2. Meyniel, 1976, с. 339–342.
3. Маркосян, Карапетян, 1976, с. 292–296.
4. Hoàng, 1987, с. 302–312.
5. Burlet, Fonlupt, 1984, с. 225–252.
6. Hertz, 1990, с. 231–240.
7. Roussel, Rusu, 2001, с. 107–123.

Литература

• Meyniel H. On the perfect graph conjecture // Discrete Mathematics. — 1976. — Т. 16, вып. 4. — С. 339–342. — doi:10.1016/S0012-365X(76)80008-8.
• С. Маркосян, И. Карапетян. О совершенных графах // ДАН Арм. ССР. — 1976. — Вып. 5.
• Hoàng C. T. On a conjecture of Meyniel // Journal of Combinatorial Theory. — 1987. — Т. 42, вып. 3. — С. 302–312. — doi:10.1016/0095-8956(87)90047-5.
• 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:10.1016/S0304-0208(08)72938-4.
• Hertz A. A fast algorithm for coloring Meyniel graphs // Journal of Combinatorial Theory. — 1990. — Т. 50, вып. 2. — С. 231–240. — doi:10.1016/0095-8956(90)90078-E.
• Roussel F., Rusu I. An O(n²) algorithm to color Meyniel graphs // Discrete Mathematics. — 2001. — Т. 235, вып. 1—3. — С. 107–123. — doi:10.1016/S0012-365X(00)00264-8.