On NP-hardness of the clique partition -- independence number gap recognition and related problems (Q2368935): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 06:52, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On NP-hardness of the clique partition -- independence number gap recognition and related problems |
scientific article |
Statements
On NP-hardness of the clique partition -- independence number gap recognition and related problems (English)
0 references
28 April 2006
0 references
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)].
0 references
partial Latin squares completion
0 references