complexity of graph 2.5-coloring

Question

My question is inspired by this one. ​ I define 2.5-coloring to be the parameterized problem

Instance: an integer j and an n-vertex non-empty simple graph G
Parameter: integer k
Output: if there is a 3-coloring of G in which at least one of
the colors is used at most ​ min($\hspace{.03 in}$j,k) ​ times then YES else NO

.


Since j is part of the input and the only involvement of k is via ​ min($\hspace{.03 in}$j,k) , ​ increasing k
cannot make 2.5-coloring easier. ​ ​ ​ ​ Even for k=0, that problem is logspace-complete.
For k in n^Ω(1), that problem is NP-hard by enlarging 3-coloring instances.
By applying Reingold's result to the bipartite double cover of the subgraph induced by the
non-guessed vertices, 2.5-coloring is in ​ ​ GC ( max(k$\cdot \hspace{-0.02 in}\lceil \log_2(n)\hspace{-0.02 in}\rceil \hspace{-0.03 in}$,n) , DSPACE(O(log(n))) ) ,
since the verifier has two-way access to the alleged proof.

Is anything else known about the complexity of 2.5-coloring?

In particular, I'd accept any non-trivial consequence of any answer to any of the following,
since I do not expect anyone to manage to outright answer any of them:

Is 2.5-coloring in ​ coNTIME$\left(\hspace{-0.02 in}n^{o(k)}\hspace{-0.04 in}\right)\hspace{-0.07 in}\big/\hspace{-0.04 in}$$n^{o(k)}$ ? ​ ​ ​ ​ Is 2.5-coloring in rational-uniform ACC0?
Is 2.5-coloring with k in n^o(1) hard for rational-uniform TC0?
Is there a function g in ω(log) such that 2.5-coloring with k in n^o(1) is GC(g(n),AC0)-hard?
Is 2.5-coloring with k in n^o(1) hard for ​ GC ( k$\cdot$O(log(n)) , DSPACE(O(log(n))) ) ?
What about the "infinitely-often" versions of any of those questions,
i.e., for pairs k,n such that k is in n^o(1) and is arbitrarily large?

Answer 1

(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.