Weighted-Set Graph Colorings

作者:Shrock Robert*; Xu Yan
来源:Journal of Statistical Physics, 2010, 139(1): 27-61.
DOI:10.1007/s10955-010-9937-4

摘要

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.

  • 出版日期2010-4