This preprint was accepted December 2008
АННОТАЦИЯ:
Для графа с кликовым числом $n$ и максимальной степенью вершины
не более ${3n-3\over 2}$ доказывается существование независимой
{\it трансверсали} (т.е. независимого множества вершин, пересекающего
все $n$-клики этого графа). Показано, что для графа с кликовым
числом $n$ и большей максимальной степенью это утверждение неверно.
Во второй части работы выводятся новые соотношения между хроматическим
числом и степенью для графов, разбивающихся на $n$-клики.
Ключевые слова: хроматическое число, клика, трансверсаль
[Full text:
Preprint in Russian (.pdf.gz)
Back to all preprints
Back to the Steklov
Institute of Mathematics at St.Petersburg