Borodin-Kostochka conjecture and Partitioning a graph into classes with no clique of specified size

Abstract

For a given graph $H$ and the graphical properties $P_1,P_2,\dots ,P_k$, a graph $H$ is said to be $(V_1,V_2,\dots ,V_k)$-partitionable if there exists a partition of $V(H)$ into $k$-sets $V_1,V_2\dots ,V_k$, such that for each $i\in [k]$, the subgraph induced by $V_i$ has the property $P_i$. In $1979$, Bollobás and Manvel showed that for a graph $H$ with maximum degree $\Delta (H)\ge 3$ and clique number $\omega (H)\le \Delta (H)$, if $\Delta (H)=p+q$, then there exists a $(V_1,V_2)$-partition of $V(H)$, such that $\Delta (H[V_1])\le p$, $\Delta (H[V_2])\le q$, $H[V_1]$ is $(p-1)$-degenerate, and $H[V_2]$ is $(q-1)$-degenerate. Assume that $p_1\ge p_2\ge \cdots \ge p_k\ge 2$ are $k$ positive integers and ${\sum }_{i=1}^k{p}_i=\Delta (H)-1+k$. Assume that for each $i\in [k]$ the properties $P_i$ means that $\omega (H[V_i])\le p_i-1$. Is $H$ a $(V_1,\dots ,V_k)$-partitionable graph? In 1977, Borodin and Kostochka conjectured that any graph $H$ with maximum degree $\Delta (H)\ge 9$ and without $K_{\Delta (H)}$ as a subgraph, has chromatic number at most $\Delta (H)-1$. Reed proved that the conjecture holds whenever $\Delta (G)\ge 10^{14}$. When $p_1=2$ and $\Delta (H)\ge 9$, the above question is the Borodin and Kostochka conjecture. Therefore, when all $p_i$s are equal to $2$ and $\Delta (H)\le 8$, the answer to the above question is negative. Let $H$ is a graph with maximum degree $\Delta$, and clique number $\omega (H)$, where $\omega (H)\le \Delta -1$. In this article, we intend to study this question when $k\ge 2$ and $\Delta \ge 13$. In particular as an analogue of the Borodin-Kostochka conjecture, for the case that $\Delta \ge 13$ and $p_i\ge 2$ we prove that the above question is true.