Weighted Graph Colorings

Details Weighted Graph Colorings Weighted Graph Colorings

2009-08-17

arxiv.org/abs/0908.2375v1

J. Stat. Phys. 138, 496-542 (2010)

Physics

Mathematical Physics

60 pages, 6 figures

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Weighted 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 Weighted Graph Colorings, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Weighted Graph Colorings will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-19768