Weighted-Set Graph Colorings

Abstract

We study a weighted-set graph coloring problem in which one assigns $q$ colors to the vertices of a graph such that adjacent vertices have different colors, with a vertex weighting $w$ that either disfavors or favors a given subset of $s$ colors contained in the set of $q$ colors. We construct and analyze a weighted-set chromatic polynomial $Ph(G,q,s,w)$ associated with this coloring. General properties of this weighted-set chromatic polynomial are proved, and illustrative calculations are presented for various families of graphs. This study extends a previous one for the case $s=1$ and reveals a number of interesting new features.

arXiv comment44 p. latex

References in corpus (9)

• 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
• Combinatorial aspects of boundary loop models
• Structure of the Partition Function and Transfer Matrices for the Potts Model in a Magnetic Field on Lattice Strips

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 $q$-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