Многогранный граф

K-частичный граф в теории графов — это граф, вершины которого разделены на k независимых множеств.
Двудольные графы являются частным случаем k-частичных графов при k = 2.
Для любого k > 2 проверка, является ли граф k-частичным, является NP-полной задачей.
В некоторых приложениях теории графов, граф из k частей может быть задан с определенной раскраской.
Полный граф из k частей имеет ребро между каждой парой вершин из разных независимых множеств.
Полные многочастные графы являются графами, которые являются полными k-частичными для некоторого k.
Графы Турана являются частным случаем полных многочастных графов с определенными ограничениями на размер независимых множеств.
Полные графы с k-частями, полные многочастные графы и их аналоги могут быть распознаны за полиномиальное время.

Полный текст статьи:

Многодольный граф — Википедия