Search
Семинар 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$).