Membership from the library's existential second-order definition of $k$-colorability; hardness by padding the reduction of 3-colorability to $k$-colorability with $k - 3$ further colors, 3-colorability being NP-hard by the catalog's statement for it.