Achromatic Number

Input

Graph $G = (V, E)$, positive integer $K \leq |V|$.

Question

Does $G$ have achromatic number $K$ or greater, i.e. is there a partition of $V$ into disjoint sets $V_1, V_2, \dots, V_k$, $k \geq K$, such that each $V_i$ is an independent set for $G$ (no two vertices in $V_i$ are joined by an edge in $E$) and such that, for each pair of distinct sets $V_i, V_j$, $V_i \cup V_j$ is not an independent set for $G$?

Classes

• NP-complete

Comments

Remains NP-complete even if $G$ is the complement of a bipartite graph and hence has no independent set of more than two vertices.

Proofs

NP-complete

Transformation from Minimum Maximal Matching (Yannakakis & Gavril, 1980).

Reducible from

• Minimum Maximal Matching

References

• Yannakakis, M., & Gavril, F. (1980). Edge Dominating Sets in Graphs. SIAM Journal on Applied Mathematics, 38(3), 364–372. https://doi.org/10.1137/0138030