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