Пятница, 6 февраля, комната 106. Начало в 18:00.
Докладчик: А. Зыкова.
Тема: Абсолютные раскраски графов.
Abstract
Пусть вершины и ребра графа правильно покрашены в несколько цветов. Такая раскраска называется абсолютной, если цвет любого ребра не совпадает с цветом его концов. Известная гипотеза (Behzad, Vizing) гласит, что любой граф, степени вершин которого не превосходят d, можно абсолютно покрасить в не более чем d + 2 цвета. В 1998 году было доказано, что максимальное количество цветов, необходимое для такой раскраски, не превосходит
![$ d + 10^{26} $](../../../sites/default/files/tex/d92d997caa741c4c105746ddf64a2f11eb61acbd/index.png)
и
![$ d + 8 {\ln^8 d} $](../../../sites/default/files/tex/6b74210180b1742517c9481e5eeea231724fc455/index.png)
. На докладе будет рассказано о некоторых улучшениях этих оценок.