Сильная раскраска графов и сильное хроматическое число

Введение

(правильное) раскрашивание вершин

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

Сильное хроматическое число sχ(G) графа G – это наименьшее k, такое что G является сильно k-раскрашиваемым. Граф называется сильно k-хроматическим, если его сильное хроматическое число равно k.

Некоторые свойства sχ(G):
sχ(G) > Δ(G). sχ(G) ≤ 3 Δ(G) − 1. Асимптотически, sχ(G) ≤ 11 Δ(G) / 4 + o(Δ(G)). Здесь Δ(G) – максимальная степень. Сильное хроматическое число было независимо введено Алоном (1988) и Феллоусом (1990).

Связанные проблемы

При заданном графе и разбиении множества вершин, независимый трансверсаль – это множество U не смежных вершин, такое что каждая часть содержит ровно одну вершину из U. Сильная раскраска эквивалентна разбиению множества вершин на непересекающиеся независимые трансверсали (каждый независимый трансверсаль представляет собой один "цвет"). Это отличается от раскраски графа, которая представляет собой разбиение множества вершин графа на заданное количество независимых множеств, без требования, чтобы эти независимые множества были трансверсалями. Чтобы проиллюстрировать разницу между этими понятиями, рассмотрим факультет с несколькими кафедрами, где декан хочет сформировать комитет из преподавателей. Однако некоторые преподаватели находятся в конфликте и не могут работать в одном комитете. Если отношения "конфликта" представлены ребрами графа, то:

Независимое множество – это комитет без конфликтов. Независимый трансверсаль – это комитет без конфликтов, в котором ровно один представитель от каждой кафедры. Раскраска графа – это разбиение преподавателей на комитеты без конфликтов. Сильная раскраска – это разбиение преподавателей на комитеты без конфликтов, с ровно одним представителем от каждой кафедры. Таким образом, эта задача иногда называется задачей о счастливом декане.