Ниже — несколько кратких примеров того, как комбинаторика и теория графов используются в информатике, а затем решение поставленной задачи.

Примеры применения

Расписание (timetabling, job scheduling). Задачу планирования ресурсов часто формулируют как раскраску графа: вершины — задачи, ребро между задачами, которые нельзя запускать одновременно; минимальное число цветов = минимальное число временных слотов/ресурсов.Назначение в паре (matching). Поиск максимального паросочетания применяют в распределении задач работникам, в задачах о назначениях (assignment), в моделях сети обмена.Оптимизация сетей (MST, потоки, маршрутизация). Минимальные остовные деревья (MST) нужны для проектирования экономичных сетей, максимум-поток/минимальный разрез — для пропускной способности и надежности; задача кратчайших путей применяется в маршрутизации.Кодирование и коррекция ошибок. Комбинаторные конструкции (блочные коды, матрицы контрольных символов, дизайн-комбинаторика) используются для построения кодов с заданными расстояниями Хэмминга.Алгоритмическая теория сложности и случайные графы. Комбинаторика и вероятностный метод строят примеры графов с необычными свойствами (Эрдёш) и используются при оценке сложности алгоритмов.Хеширование, структуры данных и распределённые системы. Конструкции перекрывающих систем, графы разреженных паросочетаний и пр. помогают проектировать эффективные структуры хранения и отказоустойчивых сетей.

Задача: какое ограничение на хроматическое число даёт наличие простого цикла длины k в связном неориентированном графе?

Утверждение (правильная формулировка). Пусть G — связный неориентированный граф, и G содержит простой цикл C_k длины k (то есть C_k как подграф). Тогда
chi(G) ≥ chi(C_k),
а следовательно

если k чётно, chi(G) ≥ 2;если k нечётно, chi(G) ≥ 3.

Доказательство. Пусть H = C_k — подграф графа G. Любая правильная раскраска вершин G даёт при ограничении на вершины H корректную раскраску H (ничьи смежности не нарушаются при переходе к подграфу). Значит минимальное число цветов, нужное для G, не меньше минимального числа цветов, нужного для H: chi(G) ≥ chi(H) = chi(C_k). Известно, что цикл чётной длины 2-раскрашиваем (бипартитен), поэтому chi(C_k)=2 при k чётном; цикл нечётной длины не бипартитен, и chi(C_k)=3 при k нечётном. Это и даёт указанные нижние границы.

Ограничения сверху или более сильные оценки — в общем не следуют. Контрпример: наличие цикла не ограничивает сверху chi(G). Можно взять любое полное граф K_t (t произвольное) и «приклеить» к нему цикл C_k, например, добавить один мост между вершиной в K_t и вершиной в C_k. Получим связный граф, содержащий C_k, но chi(G)=t, причём t можно сделать сколь угодно большим. Значит наличие простого цикла длины k не даёт верхней границы для chi(G) и (в общем случае) не фиксирует точного значения хроматического числа, даёт лишь приведённую выше нижнюю оценку.

Замечания

Наличие треугольника (k=3) эквивалентно требованию chi(G)≥3. Наличие какого-либо нечётного цикла эквивалентно тому, что граф не бипартит (chi≥3).С другой стороны существуют графы с очень большим хроматическим числом и одновременно с большим диаметром и большой длиной наименьшего цикла (Эрдёш: графы с большой χ и большой гу́рфностью), поэтому ни малые циклы, ни их отсутствие не диктуют полностью χ.

Краткий итог: наличие простого цикла длины k гарантирует нижнюю оценку chi(G) ≥ 2 (если k чётно) или ≥ 3 (если k нечётно), но не накладывает верхнего ограничения на хроматическое число.