Weighted graph colorings

DOI10.1007/S10955-009-9882-2zbMATH Open1195.82012arXiv0908.2375OpenAlexW3100218531MaRDI QIDQ963274FDOQ963274

Authors: Shu-Chiuan Chang, Robert Shrock 

Publication date: 19 April 2010

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• An introduction to chromatic polynomials
• Exactly solved models: A journey in statistical mechanics. Selected papers with commentaries (1963-2008).
• Title not available (Why is that?)
• Title not available (Why is that?)
• Some exact results on the Potts model partition function in a magnetic field
• Boundary chromatic polynomial
• Title not available (Why is that?)
• Structural properties of Potts model partition functions and chromatic polynomials for lattice strips
• Potts model partition functions for self-dual families of strip graphs
• Ground state entropy of the Potts antiferromagnet on strips of the square lattice
• 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
• Title not available (Why is that?)

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
• Title not available (Why is that?)
• Exact results on Potts model partition functions in a generalized external field and weighted-set graph colorings
• 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
• Title not available (Why is that?)
• 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)