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

DOI10.1016/J.DISC.2006.01.004MaRDI QIDQ2368935zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Stanislav Busygin, Dmitrii V. Pasechnik

Publication date 28 April 2006

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2006.01.004

Orthogonal arrays, Latin squares, Room squares (05B15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Review text

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)].

Recommendations

Cites work

Cited in

(7)

This page was built for publication: On NP-hardness of the clique partition -- independence number gap recognition and related problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2368935)