В теории графов граф Мейнеля — это граф , в котором каждый нечетный цикл длины пять и более имеет как минимум две хорды (ребра, соединяющие непоследовательные вершины цикла). [1] Хорды могут быть непересекающимися (как показано на рисунке) или пересекаться друг с другом, если их хотя бы две.
Графы Мейнеля названы в честь Анри Мейнеля (также известного благодаря гипотезе Мейнеля ), который доказал, что они являются совершенными графами в 1976 году, [2] задолго до того, как доказательство сильной теоремы о совершенных графах полностью охарактеризовало совершенные графы. Тот же результат был независимо открыт Маркосяном и Карапетяном (1976). [3]
Графы Мейнеля являются подклассом идеальных графов. Каждый индуцированный подграф графа Мейниэля является другим графом Мейниэля, и в каждом графе Мейниэля размер максимальной клики равен минимальному количеству цветов, необходимых для раскраски графа . Таким образом, графы Мейнеля соответствуют определению идеального графа, согласно которому кликовое число равно хроматическому числу в каждом индуцированном подграфе. [1] [2] [3]
Графы Мейнеля также называются очень сильно совершенными графами , потому что (как предположил Мейниэль и доказал Хоанг) они могут быть охарактеризованы свойством, обобщающим определяющее свойство сильно совершенных графов : в каждом индуцированном подграфе графа Мейнеля каждая вершина принадлежит независимое множество , пересекающее каждую максимальную клику . [1] [4]
Графы Мейниэля содержат хордальные графы , графы четности и их подклассы — интервальные графы , дистанционно-наследственные графы , двудольные графы и линейные совершенные графы . [1]
Хотя графы Мейнеля образуют очень общий подкласс идеальных графов, они не включают в себя все совершенные графы. Например, граф дома (пятиугольник только с одной хордой) идеален, но не является графом Мейнеля.
Графы Мейниэля можно распознать за полиномиальное время [5] , а некоторые задачи оптимизации графов, включая раскраску графов , которые являются NP-сложными для произвольных графов, могут быть решены за полиномиальное время для графов Мейниэля. [6] [7]