Mathematics – Combinatorics
Scientific paper
2012-04-05
Mathematics
Combinatorics
5 pages
Scientific paper
There are many variations on partition functions for graph homomorphisms or colorings. The case considered here is a counting or hard constraint problem in which the range or color graph carries a free and vertex transitive Abelian group action so that the colors are identified with the elements of this group. A Fourier transform is used to obtain an expansion for the numbers of colorings with terms indexed by isthmus free subgraphs of the domain. The terms are products of a polynomial in the edge density a of the color graph and the number of colorings of the indexing subgraph of the domain into the complementary color graph. The polynomial in a is independent of the color group and the term has order (1-a) to the r where r is the number of vertices minus the number of components in the indexing subgraph. Thus if (1-a) is small there is a main term indexed by the empty subgraph which is a polynomial in a and the first dependence on the coloring group occurs in the lowest order corrections which are indexed by the shortest cycles in the graph and are of order (1-a) to the g-1 where g is the length of these shortest cycles. The main theorem is stated as a reciprocity law. Examples are given in which the coloring groups are long cycles and products of short cycles and adjacent vertices are required to have distant rather than distinct colors. The chromatic polynomial of a graph corresponds to using any group and taking the allowed set to be the complement of the identity.
Babson Eric
Beck Matthias
No associations
LandOfFree
Counting Group Valued Graph Colorings does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Counting Group Valued Graph Colorings, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Counting Group Valued Graph Colorings will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-213274