Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4649507 | Discrete Mathematics | 2010 | 9 Pages |
Abstract
We define by minc∑{u,v}∈E(G)|c(u)−c(v)|minc∑{u,v}∈E(G)|c(u)−c(v)| the min-cost MC(G)MC(G) of a graph GG, where the minimum is taken over all proper colorings cc. The min-cost-chromatic number χM(G)χM(G) is then defined to be the (smallest) number of colors kk for which there exists a proper kk-coloring cc attaining MC(G)MC(G). We give constructions of graphs GG where χ(G)χ(G) is arbitrarily smaller than χM(G)χM(G). On the other hand, we prove that for every 3-regular graph G′G′, χM(G′)≤4χM(G′)≤4 and for every 4-regular line graph G″G″, χM(G″)≤5χM(G″)≤5. Moreover, we show that the decision problem whether χM(G)=kχM(G)=k is NP-hard for k≥3k≥3.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Robert Berke, Dieter Mitsche,