WikiDer > Подкраска

Subcoloring
Неоптимальная подкраска в четыре цвета. Объединение красного и синего цветов, а также зеленого и желтого цветов дает подкрашивание только с двумя цветами.

В теория графов, а подкрашивание это задание цвета к графикс вершины так что каждый цветовой класс побуждает непересекающееся объединение вершин клики. То есть каждый цветовой класс должен образовывать кластерный граф.

В субхроматическое число χS(г) графа г это наименьшее количество цветов, необходимых в любой подцветке г.

Подкрашивание и субхроматический номер были введены Albertson et al. (1989).

Каждые правильная окраска и колорирование графа также являются подкрасками, поэтому субхроматическое число любого графа не более чем равно кохроматическому числу, которое не более чем равно хроматическому числу.

Подкрашивание так же сложно решить, как и раскраску, в том смысле, что (как и раскраска) это НП-полный. В частности, проблема определения того, планарный граф имеет субхроматическое число не более 2, является NP-полным, даже если это

Субхроматическое число cograph можно вычислить за полиномиальное время (Fiala et al. 2003 г.). Для каждого фиксированного целого числа r можно за полиномиальное время решить, будет ли субхроматическое число интервал и перестановка графиков не превосходит r (Broersma et al. 2002 г.).

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

  • Albertson, M.O .; Jamison, R.E .; Hedetniemi, S.T .; Локк, С. К. (1989), "Субхроматическое число графа", Дискретная математика, 74 (1–2): 33–49, Дои:10.1016 / 0012-365X (89) 90196-9.
  • Броерсма, Хаджо; Фомин, Федор В .; Несетрил, Ярослав; Woeginger, Герхард (2002), "Подробнее о подкрасках", Вычисление, 69 (3): 187–203, Дои:10.1007 / s00607-002-1461-1.
  • Fiala, J .; Klaus, J .; Le, V. B .; Зайдель, Э. (2003), "Подкраски графа: сложность и алгоритмы", Журнал SIAM по дискретной математике, 16 (4): 635–650, CiteSeerX 10.1.1.3.183, Дои:10.1137 / S0895480101395245.
  • Гимбел, Джон; Хартман, Крис (2003), "Подкраски и субхроматическое число графа", Дискретная математика, 272 (2–3): 139–154, Дои:10.1016 / S0012-365X (03) 00177-8.
  • Гонсалвеш, Даниэль; Очем, Паскаль (2009), "О звездно-гусеничном древовидности", Дискретная математика, 309 (11): 3694–3702, Дои:10.1016 / j.disc.2008.01.041.
  • Монтасье, Микаэль; Очем, Паскаль (2015), «Почти раскраски: нераскрашиваемые графы и NP-полнота», Электронный журнал комбинаторики, 22 (1): # P1.57.
  • Очем, Паскаль (2017), «2-подкрашивание NP-полно для плоских графов сопоставимости», Письма об обработке информации, 128: 46–48, arXiv:1702.01283, Дои:10.1016 / j.ipl.2017.08.004.