Реберно досконалий граф це граф реберний граф якого є досконалим Еквівалентно це графи у яких кожен простий цикл непарно

Реберно-досконалий граф — це граф, реберний граф якого є досконалим. Еквівалентно, це графи, у яких кожен простий цикл непарної довжини є трикутником.

Реберно досконалий граф. Ребра в кожній двозв'язній компоненті пофарбовані в чорний колір, якщо компонента двочасткова, в синій колір, якщо компонента є тетраедром, і в червоний колір, якщо компонента є книгою трикутників.

Граф є реберно досконалим тоді і тільки тоді, коли будь-яка з його двозв'язних компонент є двочастковим графом, повним графом $K_{4}$ або книгою трикутників $K_{1,1,n}$ . Оскільки ці три типи двозв'язних компонент самі є досконалими графами, будь-який реберно-досконалий граф сам досконалий. З тієї ж причини будь-який реберно-досконалий граф є графом парності, графом Мейнеля і цілком упорядковуваним графом.

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

Див. також

Стиснутий граф — граф, у якому будь-який периферійний цикл є трикутником
Граф Мейнеля

Примітки

Trotter L. E., Jr. Line perfect graphs // . — 1977. — Т. 12, вип. 2. — С. 255–259. — DOI:10.1007/BF01593791.
Frédéric Maffray. Kernels in perfect line-graphs // . — 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). — . — 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 // . — 1978. — Т. 15. — No. 2. — P. 236–238. — DOI:10.1007/BF01609025..

[trotter-1] Trotter L. E., Jr. Line perfect graphs // . — 1977. — Т. 12, вип. 2. — С. 255–259. — DOI:10.1007/BF01593791.

[maffray-2] Frédéric Maffray. Kernels in perfect line-graphs // . — 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). — . — 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 // . — 1978. — Т. 15. — No. 2. — P. 236–238. — DOI:10.1007/BF01609025..