Пятница, 24 октября, комната 106. Начало в 18:00.
Докладчик: С. Л. Берлов.
Тема: Хроматические числа слоистых графов.
В докладе будут рассмотрены вопросы, связанные с хроматическими числами графов. В начале будет доказано, что в графе не очень большой степени (не более, чем в полтора раза большей мощности максимальной клики) существует независимая трансверсаль (то есть, независимое множество вершин, содержащих по вершине из каждой клики).
Будет получена оценка на хроматическое число -слоистого графа, т.е. такого графа, который можно представить в виде объединения непересекающихся
-клик. Оказывается, что хроматическое число такого графа равно
, если степень его вершин не превосходит
).
Если макисмальная степень -слоистого графа на
вершинах не ограничена, но размер максимальной клики равен
, то можно оценить его хроматическое число. Оценка сверху равна
. В случае четного
оценка снизу на хроматическое число практически равна
. В нечетном случае все сложнее, получена оценка снизу, дающая отклонение
от
. Кроме того, получена точная оценка для
, равная
и получены хорошие оценки для
(
) и
(
).