alt text

Правильная раскраска графа - это раскраска вершин графа таким образом, чтобы концы любого ребра были раскрашены в разные цвета.

Список - сопоставление каждой вершине графа некоторого разрешенного множества цветов в которые вершину можно покрасить.

Правильная списочная раскраска графа - это правильная раскраска графа с ограничением на список цветов для каждой вершины.

Списочное хроматическое число - это минимальное k, такое что для любого набора списков (каждый мощностью k для каждой вершины) можно указать правильную списочную раскраску графа.

задан 20 Июн '19 16:16

изменен 20 Июн '19 16:20

1

Тут известен пример, что для двудольного графа можно привести пример что его списочное хроматическое число больше двух. Рассмотрим граф на 6 вершинах: 1, 2, 3, 4, 5, 6. Обозначим через "-" факт соединения вершин. Тогда: 1-2, 1-3, 2-4, 3-4, 3-5, 4-6, 5-6. Тогда, если придать каждой вершине списки в которые их можно покрасить мощности 2 следующего вида: 1->(a,c), 2->(b,c), 3->(a,b), 4->(a,b), 5->(b,c), 6->(a,c), то получим что число 2 не подходит.

(20 Июн '19 20:10) worker
10|600 символов нужно символов осталось
2

Первые 3. Для четных циклов достаточно списков из 2 цветов, какой бы цвет не был выбран для вершины, всегда найдется цвет в списках смежных вершин, который можно выбрать без создания конфликта. Примерно то же самое рассуждение можно провести для нечетных циклов. Случай 3 можно доказать по индукции. Для случая 4, рассмотрим К3,3 со списками (1,2), (1,3), (2,3) для вершин обеих долей. Легко убедиться, что с такими списками правильной раскраски нет. Т.е., это контрпример, из которого видно, что 2 цветов недостаточно.

ссылка

отвечен 20 Июн '19 20:30

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×646

задан
20 Июн '19 16:16

показан
603 раза

обновлен
20 Июн '19 20:30

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru