Weighted Graph Colorings
arXiv:0908.2375 · doi:10.1007/s10955-009-9882-2
Abstract
We study two weighted graph coloring problems, in which one assigns colors to the vertices of a graph such that adjacent vertices have different colors, with a vertex weighting that either disfavors or favors a given color. We exhibit a weighted chromatic polynomial associated with this problem that generalizes the chromatic polynomial . General properties of this polynomial are proved, and illustrative calculations for various families of graphs are presented. We show that the weighted chromatic polynomial is able to distinguish between certain graphs that yield the same chromatic polynomial. We give a general structural formula for for lattice strip graphs with periodic longitudinal boundary conditions. The zeros of in the and planes and their accumulation sets in the limit of infinitely many vertices of are analyzed. Finally, some related weighted graph coloring problems are mentioned.
arXiv comment60 pages, 6 figures
References in corpus (11)
- Transcendentality and Crossing
- Bounds on the Complex Zeros of (Di)Chromatic Polynomials and Potts-Model Partition Functions
- Asymptotic Limits and Zeros of Chromatic Polynomials and Ground State Entropy of Potts Antiferromagnets
- Exact Potts Model Partition Functions on Ladder Graphs
- Structural Properties of Potts Model Partition Functions and Chromatic Polynomials for Lattice Strips
- Ground-State Degeneracy of Potts Antiferromagnets on Two-Dimensional Lattices: Approach Using Infinite Cyclic Strip Graphs
- Ground State Entropy of the Potts Antiferromagnet on Strips of the Square Lattice
- Families of Graphs With Chromatic Zeros Lying on Circles
- Complex-Temperature Phase Diagrams for the q-State Potts Model on Self-Dual Families of Graphs and the Nature of the Limit
- Potts Model Partition Functions for Self-Dual Families of Strip Graphs
- Some Exact Results on the Potts Model Partition Function in a Magnetic Field
Cited by in corpus (5)
- Exact Results on Potts Model Partition Functions in a Generalized External Field and Weighted-Set Graph Colorings
- Measures of Spin Ordering in the Potts Model with a Generalized External Magnetic Field
- Exact Partition Functions for the -State Potts Model with a Generalized Magnetic Field on Lattice Strip Graphs
- On the Potts model partition function in an external field
- Some Exact Results on Bond Percolation