Докажите, что списочное хроматическое число цикла на чётном числе вершин равно двум.

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

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

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

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

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

10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

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

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

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

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

отмечен:

×644

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

показан
200 раз

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

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

по почте:

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

по RSS:

Ответы

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

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