RUS  ENG
Full version
JOURNALS // Zapiski Nauchnykh Seminarov POMI // Archive

Zap. Nauchn. Sem. POMI, 2014 Volume 427, Pages 105–113 (Mi znsl6046)

Almost regular partition of a graph

K. S. Savenkov

St. Petersburg State University, St. Petersburg, Russia

Abstract: Let $k\le8$ be a positive integer and $G$ be a graph on $n$ vertices such that each vertex degree of $G$ is at least $\frac{k-1}kn$. It is proved in the paper that the vertex set of $G$ can be partitioned into several cliques of size at most $k$, such that for each positive integer $k_0<k$ there is at most one clique of size $k_0$ in this partition.

Key words and phrases: clique, partition.

UDC: 519.174.1

Received: 07.11.2014


 English version:
Journal of Mathematical Sciences (New York), 2016, 212:6, 708–713

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024