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

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

Рёберно совершенный граф. Рёбра в каждой двусвязной компоненте выкрашены в чёрный цвет, если компонента двудольная, в синий цвет, если компонента является тетраэдром, и в красный цвет, если компонента является книгой треугольников.

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

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