On NP-hardness of the clique partition -- independence number gap recognition and related problems (Q2368935)

The clique partition number \(\overline\chi(G)\) of a graph \(G\) is defined as the minimum number of cliques which partition the vertex set of \(G\). The independence number \(\alpha(G)\) is the maximum number of vertices of \(G\) such that no two of them are adjacent. It is well known that \(\alpha(G)\leq\overline\chi(G)\) while both \(\alpha\) and \(\overline\chi\) are NP-hard to compute. The authors of this note prove that it is NP-hard to decide whether \(\alpha(G)<\overline\chi(G)\) for a graph \(G\) even when a partition of its vertices into \(\overline\chi(G)\) cliques is given. Equivalently, this result states that given a graph \(G\) and a coloring of its vertices with \(\chi(G)\) colors, it is NP-hard to decide whether \(\omega(G)<\chi(G)\), where \(\omega\) and \(\chi\) denote the clique and chromatic numbers, respectively. The proof is based on a reduction from the problem of completing partial Latin squares, whose NP-completeness was proved by \textit{C. J. Colbourn} [Discrete Appl. Math. 8, 25--30 (1984; Zbl 0538.05013)].