Three problems built on one generic property, ColorableOn: a map into $k$ colors separating the pairs related by a conflict relation. KCol $k$, on graphs, asks whether the graph is $k$-colorable for a $k$ fixed once and for all, and is NP-complete for every $k \geq 3$ by a first-order reduction from 3-colorability. ChromaticNumber, on marked graphs, asks whether the chromatic number is at most $k$ where $k$ is the cardinality of the marked set, the unary representation of a threshold; this is Karp's CHROMATIC NUMBER, and it is NP-hard by an ordered first-order reduction from 3-colorability. CliqueCover, on the same vocabulary, asks whether the vertices can be covered by at most $k$ cliques; a clique cover is a proper coloring of the complement graph, so the first-order interpretation complementing the edges off the diagonal reduces Chromatic Number to Clique Cover.

The two threshold problems take their conflict relation off the diagonal, so they are about the underlying loopless graph. Their existential second-order definitions guess a coloring in palette form, a map into the marked set itself, since the number $k$ is not available to a formula.