Хроматическое число / k-раскрашиваемость Всем доброе время суток. Столкнулся я недавно с задачей, в рамках которой надо проверять, что данный граф [раскрашиваем](http://ru.wikipedia.org/wiki/%D0%A0%D0%B0%D1%81%D0%BA%D1%80%D0%B0%D1%81%D0%BA%D0%B0_%D0%B3%D1%80%D0%B0%D1%84%D0%B0) в $k$ цветов. Специфика следующая: - графы довольно большие (до нескольких тысяч вершин), но не очень плотные (средняя степень около 10-20, максимальная степень может быть порядка 50). - $k$ не слишком большое (до 10 примерно). - важно, чтобы результат был достоверным (т.е. даже односторонняя ошибка не допускается). Я нашел [либу](http://keithbriggs.info/very_nauty.html), которая умеет считать хроматическое число графа (надо сказать, что для таких масштабов она в среднем довольно быстро находит ответ, но на некоторых инстансах все же сильно задумывается). $k$-раскрашиваемость заведомо проще, чем подсчет хроматического числа, поэтому специализированное решение для раскрашиваемости должно бы работать получше; однако найти готовый код или хо...

Full text and comments »