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