complexity of graph 2.5-coloring 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 no(1) hard for rational-uniform TC0?

Is there a function g in ω(log) such that 2.5-coloring with k in no(1) is GC(g(n),AC0)-hard?

Is 2.5-coloring with k in no(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 no(1) and is arbitrarily large?
(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.