Известно ли следующее утверждение?
Утверждение : для любого графа с вершинами существует раскраска такая, что каждое независимое множество окрашивается не более чем цветами.n G O ( √
источник
Известно ли следующее утверждение?
Утверждение : для любого графа с вершинами существует раскраска такая, что каждое независимое множество окрашивается не более чем цветами.n G O ( √
Следующее утверждение известно мне, но может не учитываться, потому что оно неопубликовано: любой граф на вершинах может быть раскрашен таким образом, чтобы любой индуцированный подграф хроматического числа не более использовал не более цветов, где .H k χ ( H ) + B B ( B + 1 ) ≤ 2 k n
Это доказательство по индукции; мотивация состояла в том, чтобы рассмотреть раскраски, которые используют несколько цветов не только на графике, но и на всех индуцированных подграфах. Я не знаю ни о каких опубликованных результатах, все же.
Не совсем то, что вы просите, но вот нижняя граница - график, для которого любая раскраска приведет к независимому набору, окрашенному цветами:
Возьмите копии и соедините все вершины с одной вершиной . K √ с
Очевидно, что каждый набор вершин из разных является независимым, и в каждой копии вы можете найти хотя бы один «новый» цвет. KK √
Эта нижняя граница может быть легко улучшена до или около того, если мы соединяем с одной вершиной, но она остается только цветами . К1,К2,. , Ω( √
источник