Граф Мейнеля
Граф Мейнеля — це граф, у якому будь-який непарний цикл довжини п'ять і більше має принаймні дві хорди, тобто два ребра, що з'єднують несусідні вершини циклу[1]. Хорди можуть бути такими, що не перетинаються (як на малюнку), а можуть і перетинатися.
Графи Мейнеля названо ім'ям Генрі Мейнеля (відомого також за гіпотезою Мейнеля), який 1976 року довів, що вони є досконалими графами[2] задовго до доведення сильної теореми про досконалі графи, яка повністю описує досконалі графи. Той самий результат незалежно виявили Маркосян і Карапетян[3].
Досконалість ред.
Графи Мейнеля є підкласом досконалих графів. Будь-який породжений підграф графа Мейнеля є іншим графом Мейнеля і в будь-якому графі Мейнеля розмір найбільшої кліки дорівнює найменшому числу кольорів, необхідних для розфарбовування графа. Таким чином, графи Мейнеля задовольняють визначенню досконалих графів, що в будь-якому породженому підграфі число клік дорівнює хроматичному числу[1][2][3].
Графи Мейнеля називають також дуже сильно досконалими графами, оскільки (як припустив Мейнель і довів Хланг[1]) їх можна описати властивістю, яка узагальнює визначення властивості строго досконалих графів — у будь-якому породженому підграфі графа Мейнеля будь-яка вершина належить незалежній множині, котра перетинається з будь-якою максимальною клікою[1][4].
Пов'язані класи графів ред.
Графи Мейнеля містять хордальні графи, графи парності та їх підкласи, інтервальні графи, дистанційно-успадковувані графи, двочасткові графи та реберно-досконалі графи[1].
Хоча графи Мейнеля утворюють дуже загальний підклас графів, вони не включають усіх досконалих графів. Наприклад, будиночок (п'ятикутник з однією хордою) досконалий, але графом Мейнеля не є.
Алгоритми та складність ред.
Графи Мейнеля можна розпізнати за поліноміальний час[5] та деякі задачі оптимізації на графах, зокрема, розфарбовування графів, які NP-складні для довільних графів, можна розв'язати за поліноміальний час для графів Мейнеля[6][7].
Примітки ред.
- ↑ а б в г д Meyniel graphs [Архівовано 2019-07-28 у Wayback Machine.], Information System on Graph Classes and their Inclusions, retrieved 2016-09-25.
- ↑ а б Meyniel, 1976, с. 339–342.
- ↑ а б Маркосян, Карапетян, 1976, с. 292–296.
- ↑ Hoàng, 1987, с. 302–312.
- ↑ Burlet, Fonlupt, 1984, с. 225–252.
- ↑ Hertz, 1990, с. 231–240.
- ↑ Roussel, Rusu, 2001, с. 107–123.
Література ред.
- Meyniel H. On the perfect graph conjecture // Discrete Mathematics. — 1976. — Т. 16, вип. 4. — С. 339–342. — DOI:.
- С. Маркосян, И. Карапетян. О совершенных графах // ДАН Арм. ССР. — 1976. — Т. LXIII, вип. 5.
- Hoàng C. T. On a conjecture of Meyniel // Journal of Combinatorial Theory. — 1987. — Т. 42, вип. 3. — С. 302–312. — (Series B). — DOI:.
- 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:
- Hertz A. A fast algorithm for coloring Meyniel graphs // Journal of Combinatorial Theory. — 1990. — Т. 50, вип. 2. — С. 231–240. — (Series B). — DOI:.
- Roussel F., Rusu I. An O(n2) algorithm to color Meyniel graphs // Discrete Mathematics. — 2001. — Т. 235, вип. 1—3. — С. 107–123. — DOI:.