Сильная окраска
В теории графов сильная раскраска , относительно разбиения вершин на (непересекающиеся) подмножества одинакового размера, — это (правильная) раскраска вершин , в которой каждый цвет появляется ровно один раз в каждой части. Граф является сильно k -раскрашиваемым , если для каждого разбиения вершин на множества размера k он допускает сильную раскраску. Когда порядок графа G не делится на k , мы добавляем к G изолированные вершины ровно настолько, чтобы сделать порядок нового графа G ′ делящимся на k . В этом случае сильная раскраска G ′ за вычетом ранее добавленных изолированных вершин считается сильной раскраской G . [1]
Сильное хроматическое число sχ( G ) графа G — это наименьшее k такое, что G является сильно k -раскрашиваемым. Граф является сильно k -хроматическим, если он имеет сильное хроматическое число k .
Некоторые свойства sχ( G ):
- sχ( G ) > Δ( G ).
- sχ( G ) ≤ 3 ∆( G ) − 1. [2]
- Асимптотически sχ( G ) ≤ 11 Δ( G ) / 4 + o(Δ( G )). [3]
Здесь Δ( G ) — максимальная степень .
Сильное хроматическое число было независимо введено Алоном (1988) [4] [5] и Феллоузом (1990). [6]
Связанные проблемы
При наличии графа и разбиения вершин независимая трансверсаль — это множество U несмежных вершин, такое, что каждая часть содержит ровно одну вершину из U. Сильная раскраска эквивалентна разбиению вершин на непересекающиеся независимые трансверсали (каждая независимая трансверсаль — это один «цвет»). Это отличается от раскраски графа , которая представляет собой разбиение вершин графа на заданное число независимых множеств , без требования, чтобы эти независимые множества были трансверсалями.
Чтобы проиллюстрировать разницу между этими концепциями, рассмотрим факультет с несколькими отделениями, где декан хочет создать комитет из членов факультета. Но некоторые члены факультета находятся в конфликте и не будут сидеть в одном комитете. Если отношения «конфликта» представлены ребрами графа, то:
- Независимый набор — это комитет, в котором нет конфликтов.
- Независимый трансверсальный комитет — это комитет, в котором нет конфликтов и в который входит ровно по одному представителю от каждого отдела.
- Раскраска графа — это разбиение преподавателей на комитеты, не имеющие конфликтов.
- Сильная окраска — это разбиение членов факультета на комитеты без конфликта и с ровно одним членом от каждого факультета. Поэтому эту проблему иногда называют проблемой счастливого декана . [7]
Ссылки
- ^ Дженсен, Томми Р. (1995). Проблемы раскраски графов. Тофт, Бьярне. Нью-Йорк: Wiley. ISBN 0-471-02865-7. OCLC 30353850.
- ^ Хакселл, П.Е. (2004-11-01). «О сильном хроматическом числе». Комбинаторика, вероятность и вычисления . 13 (6): 857–865. doi :10.1017/S0963548304006157. ISSN 0963-5483. S2CID 6387358.
- ^ Haxell, PE (2008). «Улучшенная граница для сильного хроматического числа». Журнал теории графов . 58 (2): 148–158. doi :10.1002/jgt.20300. ISSN 1097-0118. S2CID 20457776.
- ^ Алон, Н. (1988-10-01). «Линейная древовидность графов». Israel Journal of Mathematics . 62 (3): 311–325. doi : 10.1007/BF02783300 . ISSN 0021-2172.
- ^ Алон, Нога (1992). «Сильное хроматическое число графа». Случайные структуры и алгоритмы . 3 (1): 1–7. doi :10.1002/rsa.3240030102.
- ^ Феллоуз, Майкл Р. (1990-05-01). «Трансверсали разбиений вершин в графах». Журнал SIAM по дискретной математике . 3 (2): 206–215. doi :10.1137/0403018. ISSN 0895-4801.
- ^ Хакселл, П. (2011-11-01). «О формировании комитетов». The American Mathematical Monthly . 118 (9): 777–788. doi :10.4169/amer.math.monthly.118.09.777. ISSN 0002-9890. S2CID 27202372.
