stringtranslate.com

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

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

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

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

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

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

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

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

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

Граф домов идеален, но не Мейниэль

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

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

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

Рекомендации

  1. ^ Графики abcd Мейниэля, Информационная система по классам графов и их включениям, получено 25 сентября 2016 г.
  2. ^ Аб Мейниэль, Х. (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. ^ Хоанг, Коннектикут (1987), «О гипотезе Мейниэля», Журнал комбинаторной теории , серия B, 42 (3): 302–312, doi : 10.1016/0095-8956(87)90047-5 , MR  0888682.
  5. ^ Берлет, М.; Фонлупт, Дж. (1984), «Полиномиальный алгоритм распознавания графа Мейниэля», Темы об идеальных графах , North-Holland Math. Студ., вып. 88, Северная Голландия, Амстердам, стр. 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 , МР  1081227.
  7. ^ Руссель, Ф.; Русу, И. (2001), « Алгоритм O ( n 2 ) для раскрашивания графов Мейниэля», Discrete Mathematics , 235 (1–3): 107–123, doi : 10.1016/S0012-365X(00)00264-8 , МР  1829840.