Граф Мейнеля

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

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

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

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

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

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

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

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

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

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

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

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

Литература

• 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.