Граф Мейнеля

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

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

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

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

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

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

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

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

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

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

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

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

Примечания
  1. Meyniel graphs, 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.

Литература
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.