WikiDer > Подкраска

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

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

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

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

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

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

• без треугольников график с максимумом степень 4 (Гимбел и Хартман, 2003 г.) (Fiala et al. 2003 г.),
• график сопоставимости с максимальной степенью 4 (Очем 2017),
• линейный график двудольного графа максимальной степени 4 (Гонсалвес и Очем 2009),
• график с обхват 5 (Montassier & Ochem 2015).

Субхроматическое число 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.