A paritásgráf egy olyan gráf, amelyben a két csúcs közötti bármely két generált útvonal azonos paritású – vagy mindkét út páratlan hosszúságú, vagy mindkét út páros hosszúságú [1] . A gráfok ezen osztályát először Barlet és Ury tanulmányozta és nevezte el [2] .
A paritásgráfok távolság öröklött gráfokat tartalmaznak , amelyekben a két csúcs közötti bármely két generált útvonal azonos hosszúságú. Ide tartoznak a kétrészes gráfok is , amelyek hasonlóan leírhatók olyan gráfokként, amelyekben a két csúcs közötti bármely két (nem feltétlenül generált) útvonal azonos paritású, valamint az él-tökéletes gráfok , amelyek általánosítják a bipartit gráfokat.
Bármely paritásgráf Meynel-gráf , azaz olyan gráf, amelyben bármely páratlan hosszúságú (5-ös vagy hosszabb) ciklusnak legalább két akkordja van. Egy paritásgráfban bármely hosszú ciklus két különböző paritású útra bontható, amelyek egyike sem egy él, és legalább egy akkord szükséges ahhoz, hogy ezek az utak ne legyenek generált útvonalak. Majd miután a ciklust két útra osztottuk az első akkord végpontjai között, szükség van egy második akkordra, hogy a második út ne keletkezzen. Mivel a Meinel-gráfok tökéletes gráfok , a paritásgráfok is tökéletesek [1] . Pontosan ezek azok a gráfok, amelyeknek egyetlen élű közvetlen szorzata tökéletes gráf marad [3] .
Egy gráf akkor és csak akkor paritásgráf, ha a felosztásának bármely komponense vagy teljes gráf , vagy kétrészes gráf . E leírás alapján ellenőrizhető, hogy egy gráf lineáris időben paritásgráf-e . Ugyanez a leírás néhány optimalizálási algoritmus általánosításához vezet a gráfokon, a kétrészes gráfokról a paritásgráfokra. Pl. gráffelosztással meg lehet találni egy paritásgráf súlyozott legnagyobb független halmazát polinomidőben [4] .