Meynielův graf - Meyniel graph

V Meynielově grafu musí mít každý dlouhý lichý cyklus (například zde zobrazený černý 5-cyklus) alespoň dva akordy (zelené)

v teorie grafů, a Meynielův graf je graf, ve kterém každý lichý cyklus délky pět nebo více má alespoň dva akordy, hrany spojující nenasledující vrcholy cyklu.[1] Akordy mohou být nepřekřížené (jak je znázorněno na obrázku), nebo se mohou křížit navzájem, pokud jsou alespoň dva.

Meyniel grafy jsou pojmenovány po Henri Meyniel (také známý pro Meynielův dohad ), kteří prokázali, že jsou perfektní grafy v roce 1976,[2] dlouho před dokladem o silná dokonalá věta o grafu úplně charakterizoval dokonalé grafy. Stejný výsledek nezávisle objevil Markosjan a Karapetjan (1976).[3]

Dokonalost

Meynielské grafy jsou podtřídou dokonalých grafů. Každý indukovaný podgraf Meynielova grafu je další Meynielův graf a v každém Meyniel grafu je velikost a maximální klika se rovná minimálnímu počtu barev potřebných v a zbarvení grafu. Meynielské grafy tedy splňují definici dokonalého grafu, že počet klik se rovná chromatickému číslu v každém indukovaném podgrafu.[1][2][3]

Meynielské grafy se také nazývají velmi silně dokonalé grafy, protože (jak Meyniel předpokládal a Hoàng dokázal) je lze charakterizovat vlastností zobecňující definující vlastnost silně dokonalé grafy: v každém indukovaném podgrafu Meynielova grafu patří každý vrchol k nezávislá sada který protíná všechny maximální klika.[1][4]

Související třídy grafů

Meynielovy grafy obsahují chordální grafy, paritní grafy a jejich podtřídy intervalové grafy, vzdálenostně dědičné grafy, bipartitní grafy, a řádkové perfektní grafy.[1]

Domácí graf je dokonalý, ale ne Meyniel

Ačkoli Meyniel grafy tvoří velmi obecnou podtřídu dokonalých grafů, nezahrnují všechny dokonalé grafy. Například domácí graf (pětiúhelník s pouze jedním akordem) je dokonalý, ale nejde o Meynielův graf.

Algoritmy a složitost

Meyniel grafy lze rozpoznat v polynomiální čas,[5] a několik problémů s optimalizací grafů včetně zbarvení grafu to jsou NP-tvrdé pro libovolné grafy lze vyřešit v polynomiálním čase pro Meyniel grafy.[6][7]

Reference

  1. ^ A b C d Meyniel grafy, Informační systém o třídách grafů a jejich zahrnutí, vyvoláno 2016-09-25.
  2. ^ A b Meyniel, H. (1976), „O dokonalém dohadu grafu“, Diskrétní matematika, 16 (4): 339–342, doi:10.1016 / S0012-365X (76) 80008-8, PAN  0439682.
  3. ^ A b Markosjan, S.E .; Karapetjan, I. A. (1976), „Perfect graphs“, Doklady Akademiya Nauk Armyanskoĭ SSR, 63 (5): 292–296, PAN  0450130.
  4. ^ Hoàng, C. T. (1987), „O domněnce Meyniel“, Journal of Combinatorial Theory, Řada B, 42 (3): 302–312, doi:10.1016/0095-8956(87)90047-5, PAN  0888682.
  5. ^ Burlet, M .; Fonlupt, J. (1984), „Polynomiální algoritmus pro rozpoznání Meynielova grafu“, Témata o dokonalých grafech, North-Holland Math. Stud., 88, Severní Holandsko, Amsterdam, s. 225–252, doi:10.1016 / S0304-0208 (08) 72938-4, hdl:10068/49205, PAN  0778765.
  6. ^ Hertz, A. (1990), „Rychlý algoritmus pro barvení Meyniel grafů“, Journal of Combinatorial Theory, Řada B, 50 (2): 231–240, doi:10.1016 / 0095-8956 (90) 90078-E, PAN  1081227.
  7. ^ Roussel, F .; Rusu, I. (2001), „An Ó(n2) algoritmus pro barevné Meyniel grafy ", Diskrétní matematika, 235 (1–3): 107–123, doi:10.1016 / S0012-365X (00) 00264-8, PAN  1829840.