Слабо алмазо-свободный граф

Материал из WikiGrapp
Перейти к:навигация, поиск

Слабо алмазо-свободный граф (Weakly diamond-free graph) — Пусть вершина V такова, что ее степень не превышает 2\omega(G) - 1, где \omega(G)плотность графа G, и окрестность N(v) порождает алмазо-свободный подграф. Назовем ее WDF-вершиной. Граф называется WDF-графом, если каждый индуцированный подграф содержит WDF-вершину. Класс WDF-графов содержит хордальные и совершенные реберные графы.

Литература

  • [Discrete Math.]