Can we minimize the sum of the colors instead of the number of colors? Answer: No.
Take the following counter-example, which is a $K_4$ with a couple of attached triangles:
using GraphPlot
using Graphs
g = simple_graph(12,is_directed=false)
E = union([(i,j) for i in 1:4 for j in i+1:4],[(i,j) for i in 5:6, j in [1,4]],[(i,j) for i in 7:8, j in [3,4]],[(i,j) for i in 9:10, j in [2,3]],[(i,j) for i in 11:12, j in [1,2]])
for e in E add_edge!(g,e[1],e[2]) end
gplot(g)
The standard model shows that the graph is 4-colorable:
using JuMP
using GLPKMathProgInterface
m = Model(solver=GLPKSolverMIP())
C=collect(1:num_vertices(g)) # colors
@variable(m, c[1:num_vertices(g)], Bin)
@variable(m, x[1:num_vertices(g),C], Bin)
@objective(m, Min, sum(c[i] for i in C))
@constraints(m, begin
[v in 1:num_vertices(g)], sum(x[v,j] for j in C)==1
[i in C, e in edges(g)], x[source(e,g),i]+x[target(e,g),i] <= 1
[i in C], num_vertices(g)*c[i] >= sum(x[v,i] for v in 1:num_vertices(g))
end)
solve(m)
println("The graph is $(Int(getobjectivevalue(m)))-colorable.")
The graph is 4-colorable.
using Colors
nodefillc = distinguishable_colors(num_vertices(g), colorant"red")
vcolor=copy(nodefillc)
for v=1:num_vertices(g), c in C
if getvalue(x[v,c])>0.5
vcolor[v]=nodefillc[c]
end
end
gplot(g,nodefillc=vcolor)
Now let's see what happens in the alternative "sum of colors model":
m = Model(solver=GLPKSolverMIP())
C=collect(1:num_vertices(g)) # colors
@variable(m, c[1:num_vertices(g)], Int)
@variable(m, x[1:num_vertices(g),C], Bin)
@objective(m, Min, sum(c[i] for i in C))
@constraints(m, begin
[v in 1:num_vertices(g)], sum(x[v,j] for j in C)==1
[i in C, e in edges(g)], x[source(e,g),i]+x[target(e,g),i] <= 1
[v in 1:num_vertices(g)], c[v] == sum(i*x[v,i] for i in C)
end)
solve(m)
# extract the colors
colors=[Int(getvalue(c[i])) for i=1:num_vertices(g)]
println("The graph is $(length(unique(colors)))-colorable.")
The graph is 5-colorable.
nodefillc = distinguishable_colors(num_vertices(g), colorant"blue")
vcolor=copy(nodefillc)
for v=1:num_vertices(g), c in C
if getvalue(x[v,c])>0.5
vcolor[v]=nodefillc[c]
end
end
gplot(g,nodefillc=vcolor)