# Coloring vertices in a cubic lattice graph and counting edges between vertices of identical and vertices of distinct coloration

Take an $A \times B \times C$ cubic lattice graph $G$, and paint $k_1$ vertices with color $c_1$ & $k_2$ vertices with color $c_2$, where $(k_1 + k_2)$ is equal to the total vertex count. Let $s_1$ be the number of edges between vertices of identical coloration, and $s_2$ be the number of edges between vertices of distinct coloration. How many pairs $(s_1, s_2)$ exist?

Also, is it known how many distinct total colorations of $G$, with $k_1$ and $k_2$ colors of type $c_1$ and $c_2$, respectively, exist up to rotational & reflectional symmetry of the graph?

Edit: I need to specify that, in the above problem, $k_1$ and $k_2$ are exactly specified, and I am looking for an exact counting solution as a function of $A$, $B$, and $C$ (i.e. as a function of the edge lengths of the cubic lattice). I apologize for any confusion this may have caused.

Edit 2: Actually I would also be perfectly happy with an exact counting solution where $A$, $B$, and $C$ are exactly specified, and we have an exact counting solution as a function of $k_1$ and $k_2 = (A*B*C) - k_1$.

• I believe the number of impossible pairs of s's is less than d^2, for d the maximal degree of the graph, which should be 6. Indeed, using an incremental checkerboard coloring allows us to add 3 or 4 or 5 or 6 edges to one of the totals, giving us something similar to a numerical semigroup of possibilities. Other colorings may take us to O(d) exceptions. As for distinct colorings, most are asymmetric, so there are about 2^(v-4) distinct colorings up to symmetry on the v many vertices. Mar 5 '14 at 0:24
• Note that the above remarks extend to general bipartite graphs, although the v-4 term may need tweaking. Mar 5 '14 at 0:29
• If the k's are fixed in advance, the number changes, but again starting with a partial checkerboard coloring, one arrives at a stamp or coin problem which has been studied. Similarly, most colorings with fixed k are assymetrical, so dividing by 8 or by 16 gets you in the ballpark. Mar 5 '14 at 0:34
• @TheMaskedAvenger Terrific comments - I'm hoping an exact counting solution is possible though, at least for a class of cases, and I'm working on that.
– Mfms
Mar 5 '14 at 0:39
• Ok. It is unclear what are the parameters. Do you want a function of A B and C, or are the k's also given as input? Please edit the question to clarify. Mar 5 '14 at 0:53

If you take a coloring and tweak it by switching the colors on two vertices of opposite color, you land in the same class of colorings $(k_1,k_2)$ while making an incremental change in the s values of any number from 0 up to twice the maximal degree D in the graph, since you have vertex degrees ranging over all values in [D/2,D]. I expect the s values to range over a large interval, missing at most D values near the ends of the interval, and only when $k_1$ or $k_2$ is smaller than D.
Using a checkerboard coloring, $s_2$ can be pushed toward $Dk_1$ until you run out of colors or edges. Using a compact coloring, one can push $s_2$ down to AB + A + 1 or slightly lower depending on $k_1$ being a large enough multiple of A or AB. When $k_1$ is smaller than A a different analysis will be needed. I assume A< B< C. (So it may be that A is the limiting factor more than D in the previous paragraph.)
I think that this can be reframed in terms of general bipartite graphs and can benefit from research on numerical semigroups and the Frobenius coin problem. In particular, I do not see constraints that indicate large exceptional values for $s_2$.