In this paper, we resolve all remaining open cases of the complexity of computing the generalized coloring numbers.
For the weak coloring numbers, we complete the work of Grohe et al. [1]} by showing that the weak 2-coloring number is NP-hard to compute.
Our reduction uses 2-Clause 3-SAT in contrast to Balanced Complete Bipartite Subgraph as in [1]}.
For the coloring numbers, we use another reduction from 2-Clause 3-SAT to prove that the \(r\) -coloring number is NP-hard to compute for all \(r \ge 2\) .
