Weighted graph colorings (Q963274)

The authors study proper \(q\)-colorings of the vertices of a graph with a weighting factor \(\omega\) that either disfavors or favors a given color. In particular, the authors analyze a weighted chromatic polynomial \(Ph(G, q, \omega)\) associated with this problem, which generalizes the chromatic polynomial \(P(G, q)\). A number of interesting properties of the weighted chromatic polynomial are found. It is shown how it encodes more information about the graph \(G\), as shown by the fact that it is able to distinguish between certain graphs that yield the same chromatic polynomial. Some formulas for \(Ph(G, q, \omega)\) for various families of graphs \(G\) are given, including line graphs, star graphs, complete graphs, and cyclic lattice strip graphs. The zeros of \(Ph(G, q, \omega)\) in the \(q\) and \(\omega\) planes and their accumulation sets in the limit of infinitely many vertices of \(G\) are discussed. Some related weighted graph coloring problems are mentioned.