JUCS - Journal of Universal Computer Science 7(12): 1114-1124, doi: 10.3217/jucs-007-12-1114
A Generic NP-hardness Proof for a Variant of Graph Coloring
expand article infoHans L. Bodlaender‡
‡ Institute of Information and Computing Sciences, Utrecht University, Netherlands

Corresponding author: Hans Bodlaender ( hansb@cs.uu.nl )

© Hans Bodlaender.
This article is freely available under the J.UCS Open Content License.
Citation: Bodlaender HL (2001) A Generic NP-hardness Proof for a Variant of Graph Coloring. JUCS - Journal of Universal Computer Science 7(12): 1114-1124. https://doi.org/10.3217/jucs-007-12-1114
Open Access
Abstract
In this note, a direct proof is given of the NP-completeness of a variant of GRAPH COLORING, i.e., a generic proof similar to the proof of Cook of the NP-completeness of SATISFIABILITY. Then, transformations from this variant of GRAPH COLORING to INDEPENDENT SET and to SATISFIABILITY are shown. These proofs could be useful in an educational setting, where basics of the theory of NP-completeness must be explained to students whose background in combinatorial optimisation and/or graph theory is stronger than their background in logic. In addition, I believe that the proof given here is slightly easier than older generic proofs of NP-completeness.
Keywords
NP-completeness, computational complexity, graphs, education