complexity of graph 2.5-coloring
(I now realize that one of the questions I gave at the bottom of my OP is trivial,

and for another, a yes answer would have a simple unlikely consequence.

As I stated in my OP, 2.5-coloring is logspace-complete even with k=0,

so it certainly is hard for TC0, and if it's in ACC0 then ​ ACC0 = logspace .)

More interestingly, I recently learned about the odd cycle transversal problem. ​ By using Reingold's algorithm as I mentioned in my OP, odd cycle transversal is logspace-equivalent to 2.5-coloring. ​ Accordingly, this paper yields a significant amount of information

"about the complexity of 2.5-coloring", and this paper gives a faster algorithm for it.