An $n×m$ rectangle consisting of $nm$ total squares is to be arranged such that no orthogonally-adjacent squares have same color and no more than one pair from each color are diagonally-adjacent. What is the minimum number of different colors $\underset{\text{min}}{x}$ (expressed as a formula in terms of $n$,$m$)?, given that $\quad n,m\:∈ℕ_{0}$,$\:\:x∈ℕ_{\:0}^{nm}$.
Beyond (or deviating from) finding answer to above: What if there were a constraint imposed that the difference between number of most- and least- represented colors must not exceed some low integer (say $2$)? $\quad$ Furthermore: Is it necessarily possible (if holding the rectangle's dimensions constant) that for any $x\:>\underset{\text{min}}{x}$integer greater than the minimum number $x$ of different colors (from $x+1$ up to maximum n∙m) it must also (still, under this added constraint) be possible to satisfy the original adjacency stipulations?
Except for particularly small values for n or m (where the diagonality restraint might allow some diagonal adjacency to reduce number of colors required), wouldn't you require 4 colors? Example:
ABABAB...
CDCDCD...
BABABA...
DCDCDC...
...
For the "Beyond" part - given that pattern, there should be very little variance between number of squares of each color rectangles with an even number of either rows or columns. If you had an odd number of both then of course you would end up with a larger number of As and Bs than Cs and Ds, and so might have to add additional colors to meet the additional constraint. Alternately you could try something like:
ABCDABCD
CDABCDAB
ABCDABCD
Though I think that ends up depending on the specific dimensions of n,m as to whether you can do it with little variation in the number of colors used.
I'm not clear at all on what is meant by the Furthermore portion...which conditions are being waived and which are necessarily retained?