In this paper, we proved that the \(r\) -coloring number (for \(r \ge 2\) ) and the weak 2-coloring number are both NP-hard to compute, resolving an open problem from [1]}. We note that our construction does not cover a few small values of the coloring number. For instance, graphs with \(r\) -coloring number 1 or 2 can be easily recognized (independent of \(r\) ) since this is equivalent to recognizing trees and series-parallel graphs respectively. This is an inherent limitation of 2-Clause 3-SAT, and will require a different technique to resolve.
