Рёберно совершенный граф — это граф, рёберный граф которого является совершенным. Эквивалентно, это графы, у которых каждый простой цикл нечётной длины является треугольником.
Граф является рёберно совершенным тогда и только тогда, когда любая из его двусвязных компонент является двудольным графом, полным графом или книгой треугольников . Поскольку эти три типа двусвязных компонент являются сами по себе совершенными графами, любой рёберно совершенный граф сам совершенен. По аналогичным причинам любой рёберно совершенный граф является графом чётности, графом Мейнеля и вполне упорядочиваемым графом.
Рёберно совершенные графы обобщают двудольные графы и разделяют с ними свойства, что наибольшее паросочетание и наименьшее вершинное покрытие имеют одинаковые размеры, а хроматический индекс равен максимальной степени.
См. также Сжатый граф — граф, в котором любой периферийный цикл является треугольником
Примечания
Категория:Совершенные графы