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]