кубічний сірниковий граф), який не є ні дистанційно-успадковуваним, ні двочастковим
Граф парності — це граф, у якому будь-які два породжені шляхи між двома вершинами мають однакову парність — або обидва мають непарні довжини, або обидва парні. Цей клас графів першим почали вивчати і дали йому назву Барлет та Урі.

Пов'язані класи графів
Графи парності включають дистанційно-успадковувані графи, в яких будь-які два породжені шляхи між двома вершинами мають однакові довжини. До них належать також двочасткові графи, які можна описати аналогічно як графи, в яких будь-які два шляхи (не обов'язково породжені) між двома вершинами мають однакову парність, і реберно-досконалі графи, що узагальнюють двочасткові графи.

Будь-який граф парності є графом Мейнеля, тобто графом, у якому будь-який цикл непарної довжини (довжиною 5 і більше) має принаймні дві хорди. У графі парності будь-який довгий цикл можна розбити на два шляхи різної парності, жоден з яких не є окремим ребром і необхідна принаймні одна хорда, щоб ці шляхи були породженими шляхами. Тоді після розбиття циклу на два шляхи між кінцевими точками першої хорди необхідна друга хорда, щоб другий шлях не був породженим. Оскільки графи Мейнеля є досконалими графами, графи парності також досконалі. Це точно графи, прямий добуток яких з окремим ребром залишається досконалим графом.

Алгоритми
Граф є графом парності тоді й лише тоді, коли будь-яка компонента його  є або повним графом, або двочастковим графом. Ґрунтуючись на цьому описі, перевірити, чи є граф графом парності можна за лінійний час. Той самий опис приводить до узагальнення деяких алгоритмів оптимізації на графах із двочасткових графів на графи парності. Наприклад, використовуючи розщеплення графа, зважену найбільшу незалежну множину графа парності можна знайти за поліноміальний час.

Примітки


Література
* 
* 
* 

