With m=n and k=2 a brute force search gives the sequence of feasible/total for m=1,... as 2/2, 14/16, 108/512, 1256/65536, ... which is not on oeis even after dividing by two to account for the label symmetry.
Edit: Removing single-color configurations and dividing by two gives http://oeis.org/A068416 which I believe corresponds to m=n, k=2 for your original question.