Неоптимальная подраскраска с четырьмя цветами. Слияние красного и синего цветов, а также зеленого и желтого цветов дает подраскраску всего с двумя цветами.
В теории графов подраскраска — это назначение цветов вершинам графа таким образом , что каждый цветовой класс индуцирует вершинное непересекающееся объединение клик . То есть каждый цветовой класс должен образовывать кластерный граф .
Субхроматическое число χ S ( G ) графа G — это наименьшее количество цветов, необходимое для любой подраскраски графа G .
Подцветка и субхроматическое число были введены Альбертсоном и др. (1989).
Каждая правильная раскраска и сораскраска графа также являются подраскрасками, поэтому субхроматическое число любого графа не больше кохроматического числа, которое не больше хроматического числа.
Подраскрашивание так же сложно решить, как и раскраску, в том смысле, что (как и раскраска) оно является NP-полным . Более конкретно, задача определения, имеет ли планарный граф субхроматическое число не более 2, является NP-полной, даже если это
Субхроматическое число кографа может быть вычислено за полиномиальное время (Fiala et al. 2003). Для каждого фиксированного целого числа r можно решить за полиномиальное время, является ли субхроматическое число интервальных и перестановочных графов не более r (Broersma et al. 2002).
Ссылки
Альбертсон, МО; Джеймисон, Р. Э.; Хедетниеми, С. Т.; Локк, С. К. (1989), «Субхроматическое число графа», Дискретная математика , 74 (1–2): 33–49, doi : 10.1016/0012-365X(89)90196-9.
Broersma, Hajo; Fomin, Fedor V.; Nesetril, Jaroslav; Woeginger, Gerhard (2002), "More About Subcolorings" (PDF) , Computing , 69 (3): 187–203, doi :10.1007/s00607-002-1461-1, S2CID 24777938.
Фиала, Дж.; Клаус, Дж.; Ле, В.Б.; Зайдель, Э. (2003), «Подцветки графов: сложность и алгоритмы», SIAM Journal on Discrete Mathematics , 16 (4): 635–650, CiteSeerX 10.1.1.3.183 , doi :10.1137/S0895480101395245.
Гимбел, Джон; Хартман, Крис (2003), «Подцветки и субхроматическое число графа», Дискретная математика , 272 (2–3): 139–154, doi : 10.1016/S0012-365X(03)00177-8.
Гонсалвес, Даниэль; Очем, Паскаль (2009), «О древовидности звезд и гусениц», Дискретная математика , 309 (11): 3694–3702, doi : 10.1016/j.disc.2008.01.041.
Монтассье, Микаэль; Охем, Паскаль (2015), «Почти раскрашенные: нераскрашиваемые графы и NP-полнота», Электронный журнал комбинаторики , 22 (1): #P1.57, arXiv : 1306.0752 , doi : 10.37236/3509, S2CID 59507.
Охем, Паскаль (2017), «2-подраскраска является NP-полной для планарных графов сравнимости», Information Processing Letters , 128 : 46–48, arXiv : 1702.01283 , doi : 10.1016/j.ipl.2017.08.004, S2CID 22108461.
