Реберно-досконалий граф — це граф, реберний граф якого є досконалим. Еквівалентно, це графи, у яких кожен простий цикл непарної довжини є трикутником.
Граф є реберно досконалим тоді і тільки тоді, коли будь-яка з його двозв'язних компонент є двочастковим графом, повним графом або книгою трикутників . Оскільки ці три типи двозв'язних компонент самі є досконалими графами, будь-який реберно-досконалий граф сам досконалий. З тієї ж причини будь-який реберно-досконалий граф є графом парності, графом Мейнеля і цілком упорядковуваним графом.
Реберно-досконалі графи узагальнюють двочасткові графи і поділяють з ними властивості, що найбільше парування і найменше вершинне покриття мають однакові розміри, а хроматичний індекс дорівнює найбільшому степеню.
Див. також Стиснутий граф — граф, у якому будь-який периферійний цикл є трикутником Граф Мейнеля
Примітки