Contele Meinel

Graficul Meinel  este un grafic în care orice ciclu impar de lungime cinci sau mai mult are cel puțin două coarde, adică două muchii care leagă vârfuri neînvecinate ale ciclului [1] . Acordurile pot fi neintersectate (ca în figură) sau se pot intersecta.

Graficele Meinel sunt numite după Henry Meinel (cunoscut și pentru conjectura lui Meinel ), care a demonstrat în 1976 că sunt grafice perfecte [2] cu mult înainte de a demonstra conjectura puternică a graficului perfect , care descrie complet graficele perfecte. Același rezultat a fost descoperit independent de Markosyan și Karapetyan [3] .

Perfecțiunea

Graficele Meinel sunt o subclasă de grafice perfecte. Orice subgraf generat al unui grafic Meinel este un alt grafic Meinel, iar în orice grafic Meinel, dimensiunea celei mai mari clicuri este egală cu cel mai mic număr de culori necesare pentru a colora graficul . Astfel, graficele Meinel satisfac definiția graficelor perfecte, că numărul clicei este egal cu numărul cromatic din orice subgraf generat [1] [2] [3] .

Graficele Meinel mai sunt numite și grafice foarte perfecte , deoarece (după cum a sugerat Meinel și Hlang au demonstrat) ele pot fi descrise printr-o proprietate care generalizează definiția proprietății graficelor strict perfecte - în orice subgraf generat al graficului Meinel, orice vârf aparține. la o mulțime independentă care se intersectează cu orice clică maximă [ 1] [4] .

Clase de grafice înrudite

Graficele Meinel conțin grafice cordale, grafice de paritate și subclasele lor, grafice de intervale , grafice moștenite pe distanță , grafice bipartite și grafice cu muchii perfecte [1] .

Deși graficele Meinel formează o subclasă foarte generală de grafice, ele nu includ toate graficele perfecte. De exemplu, o casă (un pentagon cu o singură coardă) este perfectă, dar nu este un grafic Meinel.

Algoritmi și complexitate

Graficele Meinel pot fi recunoscute în timp polinomial [5] și unele probleme de optimizare pe grafice, inclusiv colorarea graficelor , care sunt NP-hard pentru graficele arbitrare, pot fi rezolvate în timp polinomial pentru graficele Meinel [6] [7] .

Note

1. ↑ 1 2 3 4 Meyniel graphs Arhivat la 28 iulie 2019 la Wayback Machine , Information System on Graph Classes and their Inclusions, preluat 2016-09-25.
2. ↑ 12 Meyniel , 1976 , p. 339–342.
3. ↑ 1 2 Markosyan, Karapetyan, 1976 , p. 292–296.
4. ↑ Hoàng, 1987 , p. 302–312.
5. ↑ Burlet, Fonlupt, 1984 , p. 225–252.
6. ↑ Hertz, 1990 , p. 231–240.
7. ↑ Roussel, Rusu, 2001 , p. 107–123.

Literatură

• Meyniel H. Despre conjectura grafică perfectă // Matematică discretă . - 1976. - T. 16 , nr. 4 . — S. 339–342 . - doi : 10.1016/S0012-365X(76)80008-8 .
• S. Markosyan, I. Karapetyan. Pe grafice perfecte // DAN Arm. SSR. - 1976. - Emisiune. 5 .
• Hoàng CT Despre o conjectura a lui Meyniel // Journal of Combinatorial Theory . - 1987. - T. 42 , nr. 3 . — S. 302–312 . - doi : 10.1016/0095-8956(87)90047-5 .
• Burlet M., Fonlupt J. Algoritm polinomial de recunoaștere a unui graf Meyniel // Subiecte despre grafurile perfecte. - Olanda de Nord, Amsterdam, 1984. - T. 88. - S. 225-252. - (North-Holland Math. Stud.). - doi : 10.1016/S0304-0208(08)72938-4 .
• Hertz A. Un algoritm rapid pentru colorarea graficelor Meyniel // Journal of Combinatorial Theory . - 1990. - T. 50 , nr. 2 . — S. 231–240 . - doi : 10.1016/0095-8956(90)90078-E .
• Roussel F., Rusu I. Un algoritm O ( n 2 ) pentru a colora graficele Meyniel // Matematică discretă . - 2001. - T. 235 , nr. 1-3 . — S. 107–123 . - doi : 10.1016/S0012-365X(00)00264-8 .