"Записки научных семинаров ПОМИ"
Том 427, стр. 105-113
Почти регулярные разбиения графа
К. С. Савенков
С.-Петербургский
государственный университет,
Университетский пр. 28,
Петродворец, 198504 Санкт-Петербург, Россия
ostrich@flyingsteps.org
- Аннотация:
Пусть $k \le 8$ -- натуральное число, а граф $G$
на $n$ вершинах таков, что степень любой его вершины хотя
бы $\frac{k-1}{k}n$. В статье доказано, что
вершины графа $G$ можно разбить на несколько клик размера не
более $k$, при этом для любого натурального $k_0 < k$
клика размера $k_0$ будет присутствовать в разбиении не более
одного раза. Библ. -- 2 назв.
- Ключевые слова: клика, разбиение
[clique, partition]
Полный текст(.pdf)