Хроматический номер графика распределения

Question

Я разрабатываю алгоритм для нахождения хроматического числа графа и обеспечения правильной раскраски, используя это число. Для этой цели я использую двоичный поиск для поиска возможного ответа K и проверяю, возможно ли использование K с использованием генетического алгоритма. Проблема в том, что хроматические числа распределены неравномерно. Например, для графа с 1000 вершинами его хроматическое число, скорее всего, меньше 100. Таким образом, в моем бинарном поиске мне нужно не делить посередине между левой границей и правой границей, но найти середину хроматического Распределение номеров. Знаете ли вы какие-либо ресурсы, откуда я могу получить информацию об этом распределении? Я нашел источник, дающий мне некоторые детали, но для графиков с менее чем 10 узлами: http://keithbriggs.info/cgt.html.

Answer 1

Не существует значимого распределения хроматических чисел на графиках определенного размера. Фактически, чтобы определить такое распределение, вы должны сначала определить распределение на ваших входных графиках. Я опишу, что я имею в виду. Во-первых, определите P_G для распределения на ваших входных графиках. Затем рассмотрим хроматическое число как случайную величину X, которая отображает графики в целые числа. Наконец, вы получите распределение по X, вызовите P_X через P_X(X = k) = P_G( {G такой, что f(G) = k}). Я прошу прощения за грязное форматирование, дайте мне знать, если это имеет смысл.

Так что я не думаю, что вам нужно распределение хроматических чисел, потому что (1) у вас может не быть распределения по входным графам P_G и (2) было бы трудно получить закрытую форму для P_X, даже если вы имел P_G. Даже для простой модели случайных графов Эрдоша Реньи ожидаемое хроматическое число неизвестно, не говоря уже о распределении.

Вот несколько границ, которые вы можете использовать: (1) хроматическое число не больше максимальной степени + 1, (2) хроматическое число не меньше размера максимальной клики. Есть несколько других границ, на которые вы можете посмотреть, одна из которых - граница Хоффмана, хотя получить это может быть сложно, так как это требует вычисления собственных значений. Я думаю, что вашей лучшей ставкой может быть подход "разделяй и властвуй", когда вы (1) разбиваете свой график на более мелкие, возможно, перекрывающиеся подграфы и раскрашиваете их, а затем (2) комбинируете раскраски. Я мог бы предположить, что, вероятно, есть хорошие уеристы, которые делают это приблизительно, но у меня, к сожалению, нет никаких ссылок.