Граф Мейнеля

У графі Мейнеля будь-який довгий непарний цикл (такий як чорний 5-цикл, показаний тут) повинен мати принаймні дві хорди (зелені)

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

Графи Мейнеля названо ім'ям Генрі Мейнеля (відомого також за гіпотезою Мейнеля), який 1976 року довів, що вони є досконалими графами[2] задовго до доведення сильної теореми про досконалі графи, яка повністю описує досконалі графи. Той самий результат незалежно виявили Маркосян і Карапетян[3].

Досконалість

Графи Мейнеля є підкласом досконалих графів. Будь-який породжений підграф графа Мейнеля є іншим графом Мейнеля і в будь-якому графі Мейнеля розмір найбільшої кліки дорівнює найменшому числу кольорів, необхідних для розфарбовування графа. Таким чином, графи Мейнеля задовольняють визначенню досконалих графів, що в будь-якому породженому підграфі число клік дорівнює хроматичному числу[1][2][3].

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

Пов'язані класи графів

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

Будиночок є досконалим графом, але не є графом Мейнеля

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

Алгоритми та складність

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

Примітки

1. Meyniel graphs [Архівовано 2019-07-28 у Wayback Machine.], 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.

Література

• Meyniel H. On the perfect graph conjecture // Discrete Mathematics. — 1976. — Т. 16, вип. 4. — С. 339–342. — DOI:10.1016/S0012-365X(76)80008-8.
• С. Маркосян, И. Карапетян. О совершенных графах // ДАН Арм. ССР. — 1976. — Т. LXIII, вип. 5.
• Hoàng C. T. On a conjecture of Meyniel // Journal of Combinatorial Theory. — 1987. — Т. 42, вип. 3. — С. 302–312. — (Series B). — DOI:10.1016/0095-8956(87)90047-5.
• Burlet M., Fonlupt J. Polynomial algorithm to recognize a Meyniel graph // Topics on perfect graphs. — North-Holland, Amsterdam, 1984. — Т. 88. — С. 225–252. — (North-Holland Math. Stud.) — DOI:10.1016/S0304-0208(08)72938-4.
• Hertz A. A fast algorithm for coloring Meyniel graphs // Journal of Combinatorial Theory. — 1990. — Т. 50, вип. 2. — С. 231–240. — (Series B). — DOI:10.1016/0095-8956(90)90078-E.
• Roussel F., Rusu I. An O(n^2) algorithm to color Meyniel graphs // Discrete Mathematics. — 2001. — Т. 235, вип. 1—3. — С. 107–123. — DOI:10.1016/S0012-365X(00)00264-8.