Граф Мейнеля — це граф, у якому будь-який непарний цикл довжини п'ять і більше має принаймні дві хорди, тобто два ребра, що з'єднують несусідні вершини циклу. Хорди можуть бути такими, що не перетинаються (як на малюнку), а можуть і перетинатися.
Графи Мейнеля названо ім'ям Генрі Мейнеля (відомого також за гіпотезою Мейнеля), який 1976 року довів, що вони є досконалими графами задовго до доведення сильної теореми про досконалі графи, яка повністю описує досконалі графи. Той самий результат незалежно виявили Маркосян і Карапетян.
Досконалість Графи Мейнеля є підкласом досконалих графів. Будь-який породжений підграф графа Мейнеля є іншим графом Мейнеля і в будь-якому графі Мейнеля розмір найбільшої кліки дорівнює найменшому числу кольорів, необхідних для розфарбовування графа. Таким чином, графи Мейнеля задовольняють визначенню досконалих графів, що в будь-якому породженому підграфі число клік дорівнює хроматичному числу.
Графи Мейнеля називають також дуже сильно досконалими графами, оскільки (як припустив Мейнель і довів Хланг) їх можна описати властивістю, яка узагальнює визначення властивості строго досконалих графів — у будь-якому породженому підграфі графа Мейнеля будь-яка вершина належить незалежній множині, котра перетинається з будь-якою максимальною клікою.
Пов'язані класи графів Графи Мейнеля містять хордальні графи, графи парності та їх підкласи, інтервальні графи, дистанційно-успадковувані графи, двочасткові графи та реберно-досконалі графи.
Хоча графи Мейнеля утворюють дуже загальний підклас графів, вони не включають усіх досконалих графів. Наприклад, будиночок (п'ятикутник з однією хордою) досконалий, але графом Мейнеля не є.
Алгоритми та складність Графи Мейнеля можна розпізнати за поліноміальний час та деякі задачі оптимізації на графах, зокрема, розфарбовування графів, які NP-складні для довільних графів, можна розв'язати за поліноміальний час для графів Мейнеля.
Примітки
Література