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

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

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

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

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

См. также

• Сжатый граф — граф, в котором любой периферийный цикл является треугольником