Подкраска

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

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

Подокраска и субхроматическое число были введены Альбертсоном и др. (1989) .

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

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

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

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

Ссылки

Альбертсон, Миссури; Джеймисон, RE; Хедетниеми, СТ; Локк, SC (1989), «Субхроматическое число графа», Discrete Mathematics , 74 (1–2): 33–49, doi : 10.1016/0012-365X(89)90196-9 .
Броерсма, Хаджо; Фомин Федор Владимирович; Несетрил, Ярослав; Воегингер, Герхард (2002), «Подробнее о подцветах» (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), «Подраскраски и субхроматическое число графа», Discrete Mathematics , 272 (2–3): 139–154, doi : 10.1016/S0012-365X(03)00177-8 .
Гонсалвес, Даниэль; Охем, Паскаль (2009), «О древовидности звезд и гусениц», Discrete Mathematics , 309 (11): 3694–3702, doi : 10.1016/j.disc.2008.01.041 .
Монтасье, Микаэль; Очем, Паскаль (2015), «Почти-раскраски: нераскрашиваемые графы и NP-полнота» , Electronic Journal of Combinatorics , 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 .