3-раскраска: время \( O^*(2^n) \) и полиномиальная память с помощью перебора, улучшение до \( O^*(1.9^n) \); вероятностный \( O^*(1.5^n) \) алгоритм через сведение к задаче 2-выполнимости; \( O^*(1.45^n) \) через использование максимальных по включению независимых множеств. Общая задача: время \( O^*(3^n) \) и память \( O^*(2^n) \) через динамическое программирование, улучшение до \( O^*(2.45^n) \) через максимальные по включению независимые множества; время и память \( O^*(2^n) \) через формулу включений-исключений и быстрое преобразование Фурье. [Thore Husfeldt, Graph colouring algorithms]