Семинар 24 октября 2008 года

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

Докладчик: С. Л. Берлов.

Тема: Хроматические числа слоистых графов.

Abstract

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

Будет получена оценка на хроматическое число

-слоистого графа, т.е. такого графа, который можно представить в виде объединения непересекающихся

-клик. Оказывается, что хроматическое число такого графа равно

, если степень его вершин не превосходит

).

Если макисмальная степень

-слоистого графа на

вершинах не ограничена, но размер максимальной клики равен

, то можно оценить его хроматическое число. Оценка сверху равна

. В случае четного

оценка снизу на хроматическое число практически равна

. В нечетном случае все сложнее, получена оценка снизу, дающая отклонение

от

. Кроме того, получена точная оценка для

, равная

и получены хорошие оценки для

(

) и

(

).