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

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

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

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

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

См. также

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