Рёберно совершенный граф

Рёберно совершенный граф — это граф, рёберный граф которого является совершенным. Эквивалентно, это графы, у которых каждый простой цикл нечётной длины является треугольником^[1].

Граф является рёберно совершенным тогда и только тогда, когда любая из его двусвязных компонент является двудольным графом, полным графом ${\displaystyle K_{4}}$ или книгой треугольников ${\displaystyle K_{1,1,n}}$^[2]. Поскольку эти три типа двусвязных компонент являются сами по себе совершенными графами, любой рёберно совершенный граф сам совершенен^[1]. По аналогичным причинам любой рёберно совершенный граф является графом чётности^[3], графом Мейнеля^[4] и вполне упорядочиваемым графом.

Рёберно совершенные графы обобщают двудольные графы и разделяют с ними свойства, что наибольшее паросочетание и наименьшее вершинное покрытие имеют одинаковые размеры, а хроматический индекс равен максимальной степени^[5].