Эвристики раскраска графа

[salamandra91]

Необходимо найти 10 эвристик (5 по виду графа(1 рода) и 5 по алгоритму(2 рода), алгоритм полным перебором, разбиение c помощью сочетаний).
У меня пока зачтены что у дерева p=2(1 рода) , и 3 за 1:
у полного графа p=числу вершин, у кольца c четным кол-вом вершин p=2, c нечетным p=3 (1 рода).
Придумала еще ( не факт что будут зачтены):
-Если заданный граф планарный, то разбиения более чем на 4 множества вершин можно не рассматривать (2 род)
-Если граф двудольный, то хроматическое число равно 2 (1 род)
-Необходимо перебирать все возможные значения, начиная от количества вершин максимального полного подграфа данного графа (2 род)

Помогите пожалуйста придумать еще

[salamandra91]

Если что эвристики - это такие правила позволяющие либо дать ответ вообще без какого-либо алгоритма, либо упростить переборный алгоритм.