Un grafic de paritate este un grafic în care oricare două căi generate între două vârfuri au aceeași paritate - fie ambele căi au lungimi impare, fie ambele căi au lungimi pare [1] . Această clasă de grafice a fost studiată și numită pentru prima dată de Barlet și Ury [2] .
Graficele de paritate includ grafice moștenite de distanță , în care oricare două căi generate între două vârfuri au aceeași lungime. Acestea includ, de asemenea , grafuri bipartite , care pot fi descrise în mod similar ca grafuri în care oricare două căi (nu neapărat generate) între două vârfuri au aceeași paritate și grafuri cu muchii perfecte , care generalizează grafurile bipartite.
Orice grafic de paritate este un grafic Meynel , adică un grafic în care orice ciclu de lungime impară (lungime 5 sau mai mare) are cel puțin două acorduri. Într-un grafic de paritate, orice ciclu lung poate fi împărțit în două căi de paritate diferită, niciuna dintre ele nu este o singură muchie și este necesară cel puțin o coardă pentru ca aceste căi să nu fie generate căi. Apoi, după împărțirea ciclului în două căi între punctele de capăt ale primei coarde, este necesară o a doua coardă, astfel încât a doua cale să nu fie generată. Deoarece graficele Meinel sunt grafice perfecte, graficele de paritate sunt de asemenea perfecte [1] . Acestea sunt exact graficele al căror produs direct cu o singură muchie rămâne un grafic perfect [3] .
Un graf este un graf de paritate dacă și numai dacă orice componentă a diviziunii sale este fie un graf complet , fie un graf bipartit . Pe baza acestei descrieri, se poate verifica dacă un grafic este un grafic de paritate în timp liniar . Aceeași descriere conduce la o generalizare a unor algoritmi de optimizare pe grafice de la grafice bipartite la grafice de paritate. De exemplu, folosind divizarea graficului, se poate găsi cea mai mare mulțime independentă ponderată a unui grafic de paritate în timp polinomial [4] .