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 '14 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 '14 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 '14 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 '14 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 '14 at 0:53

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 '14 at 19:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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