Meinelův graf je graf, ve kterém má každý lichý cyklus o délce pět a více alespoň dva tětivy, tedy dvě hrany spojující nesousední vrcholy cyklu [1] . Akordy mohou být neprotínající se (jako na obrázku), nebo se mohou protínat.
Meinelovy grafy jsou pojmenovány po Henrym Meinelovi (také známém pro Meinelovu domněnku ), který v roce 1976 dokázal, že jde o dokonalé grafy [2], dlouho předtím, než dokázal silnou domněnku dokonalého grafu , která dokonale popisuje dokonalé grafy. Stejný výsledek nezávisle na sobě objevili Markosyan a Karapetyan [3] .
Meinelovy grafy jsou podtřídou dokonalých grafů. Jakýkoli vygenerovaný podgraf Meinelova grafu je dalším Meinelovým grafem a v každém Meinelově grafu se velikost největší kliky rovná nejmenšímu počtu barev potřebných k obarvení grafu . Meinelovy grafy tedy splňují definici dokonalých grafů, že klikové číslo se rovná chromatickému číslu v jakémkoli generovaném podgrafu [1] [2] [3] .
Meinelovy grafy se také nazývají velmi silně dokonalé grafy , protože (jak Meinel navrhl a Hlang dokázal) je lze popsat pomocí vlastnosti, která zobecňuje definici vlastnosti striktně dokonalých grafů – do jakéhokoli generovaného podgrafu Meinelova grafu patří jakýkoli vrchol na nezávislou množinu , která se protíná s libovolnou maximální klikou [1] [4] .
Meinelovy grafy obsahují akordické grafy , paritní grafy a jejich podtřídy, intervalové grafy , grafy zděděné vzdáleností , bipartitní grafy a hranově dokonalé grafy [1] .
Ačkoli Meinelovy grafy tvoří velmi obecnou podtřídu grafů, nezahrnují všechny dokonalé grafy. Například dům (pětiúhelník s jedním akordem) je dokonalý, ale není to Meinelův graf.
Meinelovy grafy lze rozpoznat v polynomiálním čase [5] a některé optimalizační problémy na grafech, včetně zbarvení grafů , které jsou NP-obtížné pro libovolné grafy, lze pro Meinelovy grafy vyřešit v polynomiálním čase [6] [7] .