Abstract | ||
---|---|---|
We generalize proper coloring of gain graphs to totally frustrated states, where each vertex takes a value in a set of 'qualities' or 'spins' that is permuted by the gain group. In standard coloring the group acts trivially or regularly on each orbit (an example is the Potts model), but in the generalization the action is unrestricted. We show that the number of totally frustrated states satisfies a deletion-contraction law. It is not matroidal except in standard coloring, but it does have a formula in terms of fundamental groups of edge subsets. One can generalize chromatic polynomials by constructing spin sets out of repeated orbits. The dichromatic and Whitney-number polynomials of standard coloring generalize to evaluations of an abstract partition function that lives in the edge ring of the gain graph. |
Year | DOI | Venue |
---|---|---|
2009 | 10.1016/j.ejc.2008.02.004 | Eur. J. Comb. |
Keywords | Field | DocType |
frame matroid,proper col- oring,permutation gain graph,edge ring,bias matroid,zero-free chromatic polynomial,totally frustrated state,gain group,fundamental group,chromatic polynomial,potts model,balanced chromatic polynomial,standard coloring,whitney-number polynomial,chromatic theory,edge subsets,gain graph,semimatroid. 1,proper coloring,frustrated state,. deletion-contraction,col,group action,satisfiability | Discrete mathematics,Complete coloring,Combinatorics,Gain graph,Fractional coloring,Polynomial,Vertex (geometry),Partition function (statistical mechanics),Brooks' theorem,Potts model,Mathematics | Journal |
Volume | Issue | ISSN |
30 | 1 | European J. Combinatorics, 30 (2009), 133-156. |
Citations | PageRank | References |
2 | 0.49 | 7 |
Authors | ||
1 |
Name | Order | Citations | PageRank |
---|---|---|---|
T. Zaslavsky | 1 | 297 | 56.67 |