Laboratory of Mathematical Logic at PDMI

Пятница, 6 февраля, комната 106. Начало в 18:00.

Докладчик: А. Зыкова.

Тема: Абсолютные раскраски графов.

Abstract

Пусть вершины и ребра графа правильно покрашены в несколько цветов. Такая раскраска называется абсолютной, если цвет любого ребра не совпадает с цветом его концов. Известная гипотеза (Behzad, Vizing) гласит, что любой граф, степени вершин которого не превосходят d, можно абсолютно покрасить в не более чем d + 2 цвета. В 1998 году было доказано, что максимальное количество цветов, необходимое для такой раскраски, не превосходит и . На докладе будет рассказано о некоторых улучшениях этих оценок.