Partitioning of a graph into induced subgraphs not containing prescribed cliques

Let $K_p$ be a complete graph of order $p\ge 2$. A $K_p$-free $k$-coloring of a graph $H$ is a partition of $V(H)$ into $V_1,V_2\dots ,V_k$ such that $H[V_i]$ does not contain $K_p$ for each $i\le k$. In 1977 Borodin and Kostochka conjectured that any graph $H$ with maximum degree $\mathrm{\Delta }(H)\ge 9$ and without $K_{\mathrm{\Delta }(H)}$ as a subgraph has chromatic number at most $\mathrm{\Delta }(H)-1$. As analogue of the Borodin-Kostochka conjecture, we prove that if $p_1\ge \cdots \ge p_k\ge 2$, $p_1+p_2\ge 7$, ${\sum }_{i=1}^k{p}_i=\mathrm{\Delta }(H)-1+k$, and $H$ does not contain $K_{\mathrm{\Delta }(H)}$ as a subgraph, then there is a partition of $V(H)$ into $V_1,\dots ,V_k$ such that for each $i$, $H[V_i]$ does not contain $K_{p_i}$. In particular, if $p\ge 4$ and $H$ does not contain $K_{\mathrm{\Delta }(H)}$ as a subgraph, then $H$ admits a $K_p$-free $\lceil \frac{\mathrm{\Delta }(H)-1}{p-1}\rceil$-coloring. Catlin showed that every connected non-complete graph $H$ with $\mathrm{\Delta }(H)\ge 3$ has a $\mathrm{\Delta }(H)$-coloring such that one of the color classes is maximum $K_2$-free subset (maximum independent set). In this regard, we show that there is a partition of vertices of $H$ into $V_1$ and $V_2$ such that $H[V_1]$ does not contain $K_p$, $H[V_2]$ does not contain $K_q$, and $V_1$ is a maximum $K_p$-free subset of V(H) if $p\ge 4$, $q\ge 3$, $p+q=\mathrm{\Delta }(H)+1$, and its clique number $\omega (H)=p$.