Раскраска графика минимизирует количество цветов в каждом независимом наборе

11

Известно ли следующее утверждение?

Утверждение : для любого графа с вершинами существует раскраска такая, что каждое независимое множество окрашивается не более чем цветами.n G O ( GnGO(n)

Игорь Шинкарь
источник

Ответы:

11

Следующее утверждение известно мне, но может не учитываться, потому что оно неопубликовано: любой граф на вершинах может быть раскрашен таким образом, чтобы любой индуцированный подграф хроматического числа не более использовал не более цветов, где .H k χ ( H ) + B B ( B + 1 ) 2 k nnHkχ(H)+BB(B+1)2kn

Это доказательство по индукции; мотивация состояла в том, чтобы рассмотреть раскраски, которые используют несколько цветов не только на графике, но и на всех индуцированных подграфах. Я не знаю ни о каких опубликованных результатах, все же.

Аравиндом
источник
10

Не совсем то, что вы просите, но вот нижняя граница - график, для которого любая раскраска приведет к независимому набору, окрашенному цветами:n

Возьмите копии и соедините все вершины с одной вершиной . Kn сKns

Очевидно, что каждый набор вершин из разных является независимым, и в каждой копии вы можете найти хотя бы один «новый» цвет. KKnKKn

Эта нижняя граница может быть легко улучшена до или около того, если мы соединяем с одной вершиной, но она остается только цветами . К1,К2,. , Ω(2nK1,K2,..Ω(n)

RB
источник
22n/3K1K2K3
2nK1K2KiG
K1K2K3
1
t2n1+2++t=n
5

α(G)nIGαIGI2,...,cKGK=KIKnαK1+nαnαn

Super8
источник
1
1+nn>nϵ>0(1+ϵ)n+Cϵ
1
n2n
(в запросе на слияние профиля) meta - хорошее место для публикации такого запроса.
Суреш Венкат