Weighted graph colorings

DOI10.1007/S10955-009-9882-2MaRDI QIDQ963274zbMATH OpenOpenAlexFDO

Authors Shu-Chiuan Chang, Robert Shrock

Publication date 19 April 2010

Published in Journal of Statistical Physics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0908.2375

zbMATH Keywords

graph coloringPotts model

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20)

Abstract: 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.

Recommendations

• Weighted-set graph colorings
• A weighted graph polynomial from chromatic invariants of knots
• Exact results on Potts model partition functions in a generalized external field and weighted-set graph colorings
• scientific article; zbMATH DE number 6004918
• Weighted coloring: further complexity and approximability results

Cites work

• scientific article; zbMATH DE number 437298 (Why is no real title available?)
• scientific article; zbMATH DE number 4091530 (Why is no real title available?)
• scientific article; zbMATH DE number 50597 (Why is no real title available?)
• scientific article; zbMATH DE number 1273988 (Why is no real title available?)
• scientific article; zbMATH DE number 503283 (Why is no real title available?)
• scientific article; zbMATH DE number 1179517 (Why is no real title available?)
• scientific article; zbMATH DE number 3007985 (Why is no real title available?)
• scientific article; zbMATH DE number 3440450 (Why is no real title available?)
• scientific article; zbMATH DE number 2199828 (Why is no real title available?)
• An introduction to chromatic polynomials
• Boundary chromatic polynomial
• Exactly solved models: A journey in statistical mechanics. Selected papers with commentaries (1963-2008).
• Ground state entropy of the Potts antiferromagnet on strips of the square lattice
• Potts model partition functions for self-dual families of strip graphs
• Some exact results on the Potts model partition function in a magnetic field
• Structural properties of Potts model partition functions and chromatic polynomials for lattice strips
• The partition function zeros in the one-dimensional q-state Potts model
• Zeroes of chromatic polynomials: A new approach to Beraha conjecture using quantum groups

Cited in

(14)

• Enumeration and structure of inhomogeneous graphs
• Edge Coloring and Decompositions of Weighted Graphs
• Totally frustrated states in the chromatic theory of gain graphs
• Edge weights and vertex colours
• Exact results on Potts model partition functions in a generalized external field and weighted-set graph colorings
• scientific article; zbMATH DE number 4144006 (Why is no real title available?)
• Exact Algorithms for Weighted Coloring in Special Classes of Tree and Cactus Graphs
• Weighted-set graph colorings
• Exact partition functions for the q-state Potts model with a generalized magnetic field on lattice strip graphs
• Measures of spin ordering in the Potts model with a generalized external magnetic field
• scientific article; zbMATH DE number 6004918 (Why is no real title available?)
• Some exact results on bond percolation
• On the Potts model partition function in an external field
• Weighted Improper Colouring

This page was built for publication: Weighted graph colorings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q963274)