Skip to main content
3 of 5
added 110 characters in body
Mfms
  • 21
  • 2

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?

Mfms
  • 21
  • 2