On the cost-chromatic number of graphs (Q1363702)

The authors consider vertex colourings in which each colour has an associated cost, incurred each time the colour is assigned to a vertex. The cost-chromatic number of a graph with respect to a cost set is the minimum number of colours necessary to produce a colouring of the graph with minimum total cost. Upper bounds are established for the cost-chromatic number, and it is shown that trees and planar blocks can have arbitrarily large cost-chromatic number. Also, it is shown that the cost-chromatic number is not monotonic with subgraph inclusion.