Сильная окраска - Strong coloring

Эта Лестница Мебиуса сильно 4-раскрашиваем. Всего 35 разделов 4-го размера, но только эти 7 разделов топологически различны.

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

В сильное хроматическое число sχ (г) графа г наименее k такой, что г сильно k-раскрашиваемый. сильно k-хроматический если у него сильное хроматическое число k.

Некоторые свойства sχ (г):

  1. sχ (г)> Δ (г).
  2. sχ (г) ≤ 3 Δ (г) − 1.[2]
  3. Асимптотически sχ (г) ≤ 11 Δ (г) / 4 + o (Δ (г)).[3]

Здесь Δ (г) это максимальная степень.

Сильное хроматическое число было независимо введено Алоном (1988).[4][5] и стипендиаты (1990).[6]

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

Для графа и разбиения вершин независимый обход это набор U несмежных вершин таких, что каждая часть содержит ровно одну вершину U. Сильная раскраска эквивалентна разбиению вершин на непересекающиеся независимые трансверсали (каждая независимая трансверсаль - это один «цвет»). Это в отличие от раскраска графика, который представляет собой разбиение вершин графа на заданное количество независимые множества, без требования, чтобы эти независимые множества были трансверсальными.

Чтобы проиллюстрировать разницу между этими концепциями, рассмотрим факультет с несколькими отделениями, где декан хочет создать комитет из преподавателей. Но некоторые преподаватели находятся в конфликте и не будут входить в состав одного комитета. Если «конфликтные» отношения представлены ребрами графа, то:

  • An независимый набор это комитет без конфликтов.
  • An независимый поперечный это комитет без конфликтов, в котором ровно по одному члену от каждого отдела.
  • А раскраска графика - это бесконфликтное разделение преподавателей на комитеты.
  • А сильная окраска представляет собой разделение преподавателей на комитеты без конфликтов и ровно по одному члену от каждого отдела. Поэтому эту проблему иногда называют проблема счастливого декана.[7]

использованная литература

  1. ^ Дженсен, Томми Р. (1995). Задачи раскраски графов. Тофт, Бьярн. Нью-Йорк: Вили. ISBN  0-471-02865-7. OCLC  30353850.
  2. ^ Хакселл, П. Э. (2004-11-01). «О сильном хроматическом числе». Комбинаторика, теория вероятностей и вычисления. 13 (6): 857–865. Дои:10.1017 / S0963548304006157. ISSN  0963-5483.
  3. ^ Хакселл, П. Э. (2008). «Улучшенная оценка сильного хроматического числа». Журнал теории графов. 58 (2): 148–158. Дои:10.1002 / jgt.20300. ISSN  1097-0118.
  4. ^ Алон, Н. (1988-10-01). «Линейная древовидность графов». Израильский математический журнал. 62 (3): 311–325. Дои:10.1007 / BF02783300. ISSN  0021-2172.
  5. ^ Алон, Нога (1992). «Сильное хроматическое число графа». Случайные структуры и алгоритмы. 3 (1): 1–7. Дои:10.1002 / RSA.3240030102.
  6. ^ Стипендиаты, Майкл Р. (1 мая 1990 г.). «Трансверсалии вершинных разбиений в графах». Журнал SIAM по дискретной математике. 3 (2): 206–215. Дои:10.1137/0403018. ISSN  0895-4801.
  7. ^ Хакселл, П. (2011-11-01). «Об образовании комитетов». Американский математический ежемесячник. 118 (9): 777–788. Дои:10.4169 / amer.math.monthly.118.09.777. ISSN  0002-9890.