Meinel-grafen är en graf där varje udda cykel av längd fem eller mer har minst två ackord, det vill säga två kanter som förbinder icke-angränsande hörn av cykeln [1] . Ackord kan vara icke-korsande (som i figuren), eller så kan de skära varandra.
Meinel-grafer är uppkallade efter Henry Meinel (även känd för Meinels gissningar ), som bevisade 1976 att de är perfekta grafer [2] långt innan han bevisade den starka perfekta grafförmodan , som fullständigt beskriver perfekta grafer. Samma resultat upptäcktes oberoende av Markosyan och Karapetyan [3] .
Meinel-grafer är en underklass av perfekta grafer. Varje genererad subgraf av en Meinel-graf är en annan Meinel-graf, och i alla Meinel-grafer är storleken på den största klicken lika med det minsta antal färger som behövs för att färga grafen . Således uppfyller Meinel-grafer definitionen av perfekta grafer, att klicknumret är lika med det kromatiska numret i vilken som helst genererad subgraf [1] [2] [3] .
Meinel-grafer kallas också mycket starkt perfekta grafer , eftersom (som Meinel föreslog och Hlang bevisade) de kan beskrivas med en egenskap som generaliserar definitionen av egenskapen för strikt perfekta grafer - i vilken som helst genererad subgraf av Meinel-grafen hör vilken vertex som helst till till en oberoende uppsättning som skär vilken maximal klick som helst [1] [4] .
Meinel-grafer innehåller ackordsgrafer , paritetsgrafer och deras underklasser, intervallgrafer , avståndsärvda grafer , tvådelade grafer och kant-perfekta grafer [1] .
Även om Meinel-grafer utgör en mycket allmän underklass av grafer, inkluderar de inte alla perfekta grafer. Till exempel är ett hus (en femhörning med ett ackord) perfekt, men det är inte en Meinel-graf.
Meinelgrafer kan kännas igen i polynomtid [5] och vissa optimeringsproblem på grafer, inklusive graffärgning , som är NP-hårda för godtyckliga grafer, kan lösas i polynomtid för Meinelgrafer [6] [7] .