Число Гранди или хроматическое число Гранди неориентированного графа — это максимальное число цветов, которые можно использовать для стратегии жадной раскраски, которая рассматривает вершины грфа последовательно и назначает каждой вершине её цвет, при этом порядок вершин выбирается таким образом, чтобы использовать как можно больше цветов. Числа Гранди названы именем П. М. Гранди,изучавшего аналогичную концепцию для ориентированных графов в 1939. Версию для неориентированных графов ввели Христен и Селков.

Примеры Путь с четырьмя вершинами даёт простейший пример графа, хроматическое число которого отличается от числа Гранди. Этот граф можно раскрасить двумя цветами, но число Гранди равно трём — если две конечные точи пути будут раскрашены первыми, жадный алгоритм раскраски использует три цвета.

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

Короны получаются из полных двудольных графов путём удаления совершенного паросочетания. В результате для каждой вершины на одной стороне графа имеется ровно одна вершина на другой стороне, которая не смежна ей. Поскольку двудольный граф может быть выкрашен в два цвета, вершины короны могут быть выкрашены этими двумя цветами, но число Гранди этого графа равно — если алгоритм жадной раскраски рассматривает каждую пару вершин по порядку, каждая вершина получит свой уникальный цвет. Как показывает этот пример, число Гранди может больше хроматического числа пропорционально числу вершин графа.

Атомы Закер определяет последовательность графов, называемых -атомами, со свойствами, что граф имеет число Гранди по меньшей мере тогда и только тогда, когда он содержит -атом. Каждый -атом строится из независимого множества и -атома путём добавления одного ребра из каждоё вершины -атома в вершине независимого множества таким образом, что каждый элемент независимого множества имеет по меньшей мере одно ребро, инцидентное ему. Раскраска Гранди -атома может быть получена путём сначала раскраски независимого множества цветом с минимальным номером, а затем раскраской оставшейся части -атома дополнительными цветами. Например, единственный 1-атом — это отдельная вершина, единственный 2-атом — отдельное ребро, но возможны два 3-атома — треугольник и путь с четырьмя вершинами.

Разреженные графы Для графа с вершинами и вырожденностью число Гранди равно . В частности, для графов с ограниченной вырожденностью (таких, как планарные графы) или для графов, у которых хроматическое число и вырожденность отличаются на постоянный множитель относительно друг друга (таких как хордальные графы), число Гранди и хроматическое число отличаются не более чем на логарифмический множитель. Для интервальных графов хроматическое число и число Гранди отличаются не более чем в 8 раз.

Вычислительная сложность Проверка, не превосходит ли число Гранди данного графа фиксированной константы , может быть выполнена за полиномиальное время путём поиска всех возможных -атомов, которые могут быть подграфами данного графа. Однако, этот алгоритм не является , поскольку экспонента во времени выполнения зависит от . Если является входной переменной, а не параметром, задача становится NP-полной. Число Гранди не превосходит единицу плюс максимальная степень графа и проверка, равно ли оно динице плюс максимальная степень графа, остаётся NP-полной задачей. Существует константа , такая что NP-трудно при использовании рандомизированных редукций аппроксимировать число Гранда с коэффициентом аппроксимации лучше, чем .

Существует точный алгоритм экспоненциального времени для вычисления числа Гранди, работающий за время .

Для деревьев и графов ограниченной древовидной ширины число Гранди может быть неограниченно велико. Тем не менее, число Гранди можно вычислить за полиномиальное время для деревьев и оно является фиксированно-параметрически разрешимым при параметризации как по древовидной ширине, так и по числу Гранди, хотя (полагая, что верна гипотеза об экспоненциальном времени) зависимость от древовидной ширины должна быть выше, чем просто экспоненциальной. Если параметризовать только по числу Гранди, оно может быть вычислено за фиксированно-параметрически разрешимое время для хордальных графов и графов без клешней, а также (используя общие результаты об изоморфизме подграфов в разреженных графах для поиска атомов) для графов с ограниченным расширением. Однако, для графов общего вида задача W-трудна, если параметризовать по числу Гранди.

Хорошо раскрашиваемые графы

Граф называется хорошо раскрашиваемым, если его число Гранди равно хроматическому числу. Проверка, является ли граф хорошо раскрашиваемым, является co-NP-сложной задачей. Наследственно хорошо раскрашиваемые графы (графы, для которых любой порождённый подграф является хорошо раскрашиваемым) — это в точности кографы (они не имеют в качестве порождённых подграфов пути с четырьмя вершинами).

Примечания

Категория:Раскраска графа Категория:Инварианты графов Категория:NP-полные задачи