Home

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

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

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

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

Abstract

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

Будет получена оценка на хроматическое число $ n $-слоистого графа, т.е. такого графа, который можно представить в виде объединения непересекающихся $ n $-клик. Оказывается, что хроматическое число такого графа равно $ n $, если степень его вершин не превосходит $ 4n/3 $).

Если макисмальная степень $ n $-слоистого графа на $ nk $ вершинах не ограничена, но размер максимальной клики равен $ n $, то можно оценить его хроматическое число. Оценка сверху равна $ nk/2 $. В случае четного $ k $ оценка снизу на хроматическое число практически равна $ nk/2 $. В нечетном случае все сложнее, получена оценка снизу, дающая отклонение $ nk/(k(k-9)) $ от $ nk/2 $. Кроме того, получена точная оценка для $ n=3 $, равная $ 8n/5 $ и получены хорошие оценки для $ k=5 $ ($ 18n/7 $) и $ k=7 $ ($ 46n/13 $).