stringtranslate.com

Граф Мейниэля

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

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

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

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

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

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

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

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

График дома идеален, но не Мейниел

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

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

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

Ссылки

  1. ^ abcd Графы Мейниэля, Информационная система по классам графов и их включениям, получено 25.09.2016.
  2. ^ ab Meyniel, H. (1976), «О гипотезе совершенного графа», Discrete Mathematics , 16 (4): 339–342, doi : 10.1016/S0012-365X(76)80008-8 , MR  0439682.
  3. ^ аб Маркосян, SE; Карапетян И.А. (1976), "Совершенные графы", Доклады Академии наук Армянской ССР , 63 (5): 292–296, MR  0450130.
  4. ^ Хоанг, CT (1987), «О гипотезе Мейниэля», Журнал комбинаторной теории , Серия B, 42 (3): 302–312, doi : 10.1016/0095-8956(87)90047-5 , MR  0888682.
  5. ^ Burlet, M.; Fonlupt, J. (1984), "Полиномиальный алгоритм распознавания графа Мейниэля", Topics on perfect graphs , North-Holland Math. Stud., т. 88, North-Holland, Amsterdam, стр. 225–252, doi :10.1016/S0304-0208(08)72938-4, hdl : 10068/49205 , MR  0778765.
  6. ^ Герц, А. (1990), «Быстрый алгоритм раскраски графов Мейниэля», Журнал комбинаторной теории , Серия B, 50 (2): 231–240, doi : 10.1016/0095-8956(90)90078-E , MR  1081227.
  7. ^ Руссель, Ф.; Русу, И. (2001), « О ( n 2 ) алгоритм для раскраски графов Мейниэля», Дискретная математика , 235 (1–3): 107–123, doi : 10.1016/S0012-365X(00)00264-8 , MR  1829840.