Рассмотрим модель плотных графов. Предложим алгоритмы полиномиальной запросовой сложности для задачи проверки графа на регулярность, а также для класса задач, связанных с разбиением графа (например, k-раскрашиваемость, поиск максимальной клики).