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

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

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

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

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

См. такжеПравить

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

ПримечанияПравить

↑ ¹ ² Trotter L. E., Jr. Line perfect graphs // Mathematical Programming. — 1977. — Т. 12, вып. 2. — С. 255–259. — doi:10.1007/BF01593791.
↑ Frédéric Maffray. Kernels in perfect line-graphs // Journal of Combinatorial Theory. — 1992. — Т. 55, вып. 1. — С. 1–8. — doi:10.1016/0095-8956(92)90028-V..
↑ Martin Grötschel, László Lovász, Alexander Schrijver. Geometric algorithms and combinatorial optimization. — 2nd. — Springer-Verlag, Berlin, 1993. — Т. 2. — С. 281. — (Algorithms and Combinatorics). — ISBN 3-540-56740-2. — doi:10.1007/978-3-642-78240-4..
↑ Annegret Wagler. Critical and anticritical edges in perfect graphs // Graph-Theoretic Concepts in Computer Science: 27th International Workshop, WG 2001, Boltenhagen, Germany, June 14–16, 2001, Proceedings. — Springer, 2001. — Т. 2204. — С. 317–327. — (Lecture Notes in Computer Science). — doi:10.1007/3-540-45477-2_29..
↑ On line-perfect graphs // Mathematical Programming. — 1978. — Т. 15. — P. 236–238. — doi:10.1007/BF01609025..

[trotter-1] ¹ ² Trotter L. E., Jr. Line perfect graphs // Mathematical Programming. — 1977. — Т. 12, вып. 2. — С. 255–259. — doi:10.1007/BF01593791.

[maffray-2] Frédéric Maffray. Kernels in perfect line-graphs // Journal of Combinatorial Theory. — 1992. — Т. 55, вып. 1. — С. 1–8. — doi:10.1016/0095-8956(92)90028-V..

[gls-3] Martin Grötschel, László Lovász, Alexander Schrijver. Geometric algorithms and combinatorial optimization. — 2nd. — Springer-Verlag, Berlin, 1993. — Т. 2. — С. 281. — (Algorithms and Combinatorics). — ISBN 3-540-56740-2. — doi:10.1007/978-3-642-78240-4..

[wagler-4] Annegret Wagler. Critical and anticritical edges in perfect graphs // Graph-Theoretic Concepts in Computer Science: 27th International Workshop, WG 2001, Boltenhagen, Germany, June 14–16, 2001, Proceedings. — Springer, 2001. — Т. 2204. — С. 317–327. — (Lecture Notes in Computer Science). — doi:10.1007/3-540-45477-2_29..

[dewerra-5] On line-perfect graphs // Mathematical Programming. — 1978. — Т. 15. — P. 236–238. — doi:10.1007/BF01609025..

[1]

[2]

[3]

[4]

[5]