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,\ldots,P_k\), a graph \(H\) is said to be \((V_1, V_2,\ldots,V_k)\)-partitionable if there exists a partition of \(V(H)\) into \(k\)-sets \(V_1, V_2\ldots,V_k\), such that for each \(i\in[k]\), the subgraph induced by \(V_i\) has the property \(P_i\). In \(1979\), Bollob\'{a}s and Manvel showed that for a graph \(H\) with maximum degree \(\Delta(H)\geq 3\) and clique number \(\omega(H)\leq \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])\leq p\), \(\Delta(H[V_2])\leq q\), \(H[V_1]\) is \((p-1)\)-degenerate, and \(H[V_2]\) is \((q-1)\)-degenerate. Assume that \(p_1\geq p_2\geq\cdots\geq p_k\geq 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])\leq p_i-1\). Is \(H\) a \((V_1,\ldots,V_k)\)-partitionable graph? In 1977, Borodin and Kostochka conjectured that any graph \(H\) with maximum degree \(\Delta(H)\geq 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) \geq 10^{14} \). When \(p_1=2\) and \(\Delta(H)\geq 9\), the above question is the Borodin and Kostochka conjecture. Therefore, when all \(p_i\)s are equal to \(2\) and \(\Delta(H)\leq 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)\leq \Delta-1\). In this article, we intend to study this question when \(k\geq 2\) and \(\Delta\geq 13\). In particular as an analogue of the Borodin-Kostochka conjecture, for the case that \(\Delta\geq 13\) and \(p_i\geq 2\) we prove that the above question is true.