Санкт-Петербургское отделение Математического института им. В.А.Стеклова РАН

ПРЕПРИНТ 24/2008


С.Л. Берлов

СООТНОШЕНИЯ МЕЖДУ КЛИКОВЫМ ЧИСЛОМ, ХРОМАТИЧЕСКИМ ЧИСЛОМ И СТЕПЕНЬЮ ДЛЯ НЕКОТОРЫХ ВИДОВ ГРАФОВ

sberlov@rambler.ru

This preprint was accepted December 2008

АННОТАЦИЯ:
Для графа с кликовым числом $n$ и максимальной степенью вершины 
не более ${3n-3\over 2}$ доказывается существование независимой 
{\it трансверсали} (т.е. независимого множества вершин, пересекающего
все $n$-клики этого графа). Показано, что для графа с кликовым 
числом $n$ и большей максимальной степенью это утверждение неверно.

Во второй части работы выводятся новые соотношения между хроматическим 
числом и степенью для графов, разбивающихся на $n$-клики.
Ключевые слова: хроматическое число, клика, трансверсаль
[Full text: Preprint in Russian (.ps.gz)
Back to all preprints
Back to the Steklov Institute of Mathematics at St.Petersburg