Реберно-досконалий граф

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

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

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

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

Див. також

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