Coloring of graphs with cost-functions whose marginal costs decrease

<p>We consider a vertex-coloring problem where the amount one pays for using a color is a function of how many times the color is used. For a cost-function <span class="math inline">\(f\)</span>, we define the <span class="math inline">\(f\)</span>-chromatic number of graph <span class="math inline">\(G\)</span> as the minimum cost of a (proper) coloring of <span class="math inline">\(G\)</span>, and focus on the case that the marginal costs <span class="math inline">\(f(i+1)-f(i)\)</span> are non-increasing. We provide bounds for general graphs, for specific classes of graphs, and for some operations on graphs. We also consider the number of colors used in an optimal coloring, and for example, characterize the trees where the bipartite coloring is not always optimal.</p>