Timeline for Coloring vertices in a cubic lattice graph and counting edges between vertices of identical and vertices of distinct coloration
Current License: CC BY-SA 3.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 5, 2014 at 19:15 | comment | added | Brendan McKay | Your second question is a simple task for Burnside's Lemma. For each symmetry, count the $(k_1,k_2)$ colourings that respect it. Sum over all symmetries and divide by the number of symmetries. | |
| Mar 6, 2014 at 17:48 | answer | added | The Masked Avenger | timeline score: 1 | |
| Mar 5, 2014 at 1:57 | history | edited | Mfms | CC BY-SA 3.0 |
added 220 characters in body
|
| Mar 5, 2014 at 0:55 | comment | added | Mfms | @TheMaskedAvenger I have updated the post! | |
| Mar 5, 2014 at 0:55 | history | edited | Mfms | CC BY-SA 3.0 |
added 292 characters in body
|
| Mar 5, 2014 at 0:53 | comment | added | The Masked Avenger | 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, 2014 at 0:39 | comment | added | Mfms | @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. | |
| Mar 5, 2014 at 0:34 | comment | added | The Masked Avenger | 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, 2014 at 0:29 | comment | added | The Masked Avenger | Note that the above remarks extend to general bipartite graphs, although the v-4 term may need tweaking. | |
| Mar 5, 2014 at 0:24 | comment | added | The Masked Avenger | 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 4, 2014 at 20:04 | history | edited | Mfms | CC BY-SA 3.0 |
added 110 characters in body
|
| Mar 4, 2014 at 19:43 | history | edited | Mfms | CC BY-SA 3.0 |
added 85 characters in body
|
| Mar 4, 2014 at 19:31 | review | First posts | |||
| Mar 4, 2014 at 19:39 | |||||
| Mar 4, 2014 at 19:15 | history | asked | Mfms | CC BY-SA 3.0 |