TY - JOUR

T1 - Weighted graph colorings

AU - Chang, Shu Chiuan

AU - Shrock, Robert

N1 - Funding Information:
Acknowledgements This research was partly supported by the grants Taiwan NSC-97-2112-M-006-007-MY3 and NSC-98-2119-M-002-001 (S.-C.C.) and U.S. NSF-PHY-06-53342 (R.S.).

PY - 2010/2

Y1 - 2010/2

N2 - We study two weighted graph coloring problems, 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 color. We exhibit a weighted chromatic polynomial Ph(G,q,w) associated with this problem that generalizes the chromatic polynomial P(G,q). 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 Ph(G,q,w) for lattice strip graphs G with periodic longitudinal boundary conditions. The zeros of Ph(G,q,w) in the q and w planes and their accumulation sets in the limit of infinitely many vertices of G are analyzed. Finally, some related weighted graph coloring problems are mentioned.

AB - We study two weighted graph coloring problems, 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 color. We exhibit a weighted chromatic polynomial Ph(G,q,w) associated with this problem that generalizes the chromatic polynomial P(G,q). 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 Ph(G,q,w) for lattice strip graphs G with periodic longitudinal boundary conditions. The zeros of Ph(G,q,w) in the q and w planes and their accumulation sets in the limit of infinitely many vertices of G are analyzed. Finally, some related weighted graph coloring problems are mentioned.

UR - http://www.scopus.com/inward/record.url?scp=77249140956&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77249140956&partnerID=8YFLogxK

U2 - 10.1007/s10955-009-9882-2

DO - 10.1007/s10955-009-9882-2

M3 - Article

AN - SCOPUS:77249140956

VL - 138

SP - 496

EP - 542

JO - Journal of Statistical Physics

JF - Journal of Statistical Physics

SN - 0022-4715

IS - 1

ER -