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

  • $\begingroup$ 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. $\endgroup$ Mar 5, 2014 at 0:24
  • $\begingroup$ Note that the above remarks extend to general bipartite graphs, although the v-4 term may need tweaking. $\endgroup$ Mar 5, 2014 at 0:29
  • $\begingroup$ 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. $\endgroup$ Mar 5, 2014 at 0:34
  • $\begingroup$ @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. $\endgroup$
    – Mfms
    Mar 5, 2014 at 0:39
  • $\begingroup$ 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. $\endgroup$ Mar 5, 2014 at 0:53

1 Answer 1


This is more a collection of potentially useful ideas and intuitions, with no guarantee of correctness and no proof.

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

  • $\begingroup$ For large A, you can pack k^3 vertices to get s_2 to be 6k^2, so the problem of small k is of independent interest. $\endgroup$ Mar 6, 2014 at 19:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.